HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 05-11

2021-05-11 21:00:47 By 张义丰

05-11——搜索 P1----------------

【广搜走地图】

/*************************************************************************
    > File Name: bfs.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 06:21:19 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, y, step;
};
int n, m, sx, sy;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[105][105];
void print(){
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            cout << mmap[i][j];
        }
        cout << endl;
    }
}
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            cin >> mmap[i][j];
            if (mmap[i][j] == 'S'){
                sx = i, sy = j;
            }
        }
    }
    queue < node> que;
    que.push((node){sx, sy, 0});
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i){
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (mmap[x][y] == 'T') {
                cout << temp.step + 1 << endl;
                print();
                return 0;
            }
            if (mmap[x][y] == '.') {
                que.push((node){x, y, temp.step + 1});
                mmap[x][y] = '@';
            }
        }
    }
    cout << "No\n";
    print();
    return 0;
}

改一下可以做为399题代码

OJ-399 小明吃饭

/*************************************************************************
    > File Name: bfs.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 06:21:19 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, y, step;
};
int n, m, sx, sy;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[505][505];
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            cin >> mmap[i][j];
            if (mmap[i][j] == '2'){
                sx = i, sy = j;
            }
        }
    }
    queue < node> que;
    que.push((node){sx, sy, 0});
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i){
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (mmap[x][y] == '3') {
                cout << temp.step + 1 << endl;
                return 0;
            }
            if (mmap[x][y] == '.') {
                que.push((node){x, y, temp.step + 1});
                mmap[x][y] = '@';
            }
        }
    }
    cout << "-1\n";
    return 0;
}

OJ-535 瓷砖

有坑!输入的行数和列数是反的。另外,结果包括起点的点

/*************************************************************************
    > File Name: 535.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 06:43:32 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, ans = 1;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[55][55];
void func(int x, int y){
    for (int i=0; i<4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] == '.') {
            ans ++;
            mmap[xx][yy] = '#';
            func(xx, yy);
        }
    }
}
int main(){
    cin >> m >> n;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            cin >> mmap[i][j];
            if (mmap[i][j] == '@') {
                sx = i, sy = j;
            }
        }
    }
    func(sx, sy);
    cout << ans << endl;
    return 0;
}

OJ-536 最大黑色区域

/*************************************************************************
    > File Name: 535.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 06:43:32 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, ans, maxn;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[105][105];
void func(int x, int y){
    for (int i=0; i<4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] == '1') {
            ans ++;
            mmap[xx][yy] = '0';
            func(xx, yy);
        }
    }
}
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            cin >> mmap[i][j];
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (mmap[i][j] == '1'){
                ans = 1;
                mmap[i][j] = '0';
                func(i, j);
                maxn = max(maxn, ans);
            }
        }
    }
    cout << maxn << endl;
    return 0;
}

OJ-397 僵尸来袭(作业)

/*************************************************************************
    > File Name: 535.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 06:43:32 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, ans;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int mmap[105][105];
void func(int x, int y){
    for (int i=0; i<4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy]) {
            mmap[xx][yy] = 0;
            func(xx, yy);
        }
    }
}
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            cin >> mmap[i][j];
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (mmap[i][j]){
                ans ++;
                mmap[i][j] = 0;
                func(i, j);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

OJ-396 填涂颜色

/*************************************************************************
    > File Name: 396.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 07:24:35 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node {
    int x, y;
};
int n, mmap[35][35];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int main(){
    cin >> n;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            cin >> mmap[i][j];
        }
    }
    queue <node> que;
    que.push((node){n+1, n+1});
    mmap[n+1][n+1] = 2;
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i){
            int x = temp.x +dir[i][0];
            int y = temp.y +dir[i][1];
            if (x< 0 || y<0 || x > n+1 || y>n+1){
                continue;
            }
            if (mmap[x][y] == 0){
                mmap[x][y] = 2;
                que.push((node){x, y});
            }
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=1;j<=n; ++j){
            if (j != 1) cout <<' ';
            if (mmap[i][j] == 1){
                cout << 1;
            }else if (mmap[i][j] == 0){
                cout << 2;
            }else {
                cout << 0;
            }
        }
        cout << endl;
    }


    return 0;
}

用了巧方法,但需要“判断边界”

OJ-404 01迷宫简易版

/*************************************************************************
    > File Name: 396.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 07:24:35 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node {
    int x, y;
};
int n, m, sx, sy, ans ;
char mmap[3005][3005];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
bool vis[3005][3005];
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        cin >> &mmap[i][1];
    }
    cin >> sx >> sy;
    queue <node> que;
    ans = 1;
    que.push((node){sx, sy});
    vis[sx][sy] = true;
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i){
            int x = temp.x +dir[i][0];
            int y = temp.y +dir[i][1];
            if (!vis[x][y] && mmap[x][y] + mmap[temp.x][temp.y]=='0'+'1'){
                ans ++;
                vis[x][y] = true;
                que.push((node){x, y});
            }
        }
    }
    cout << ans << endl;
    return 0;
}

可以通过mmap[temp.x][temp.y]+mmap[x][y]=='0'+'1'不判边界

但要注意'a'+'b'溢出的情况

OJ-405 01迷宫

自己写的代码,和田船长的区别:田船用DFS,我用BFS

/*************************************************************************
    > File Name: 405.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 07:24:35 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node {
    int x, y;
};
int n, m, k, x, y, t;
char mmap[3005][3005];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int vis[3005][3005];
queue<node> Q;
void func(int xx, int yy){
    queue<node> que;
    que.push((node){xx, yy});
    vis[xx][yy] = 1;
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i){
            int x = temp.x +dir[i][0];
            int y = temp.y +dir[i][1];
            if (!vis[x][y] && mmap[x][y] + mmap[temp.x][temp.y]=='0'+'1'){
                t ++;
                vis[x][y] = 1;
                que.push((node){x, y});
                Q.push((node){x, y});
            }
        }
    }
}
int main(){
    cin >> n >> m >> k;
    for (int i=1; i<=n; ++i) {
        cin >> &mmap[i][1];
    }
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (!vis[i][j]){
                t = 1;
                Q.push((node){i, j});
                func(i, j);
                while (!Q.empty()){
                    node temp = Q.front();
                    Q.pop();
                    vis[temp.x][temp.y] = t;
                }

            }
        }
    }
    for (int i=0; i<k; ++i) {
        cin >> x >> y;
        cout << vis[x][y] << endl;
    }
    return 0;
}

记忆化搜索,还可以进一步优化:只有当询问到的点未被计算时才进行BFS并记录相关数据

OJ_304 骑士风度的牛(作业)

OJ-398 马的遍历

船长的代码

/*************************************************************************
    > File Name: 398.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 08:34:28 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x, y, step;
};
int n, m, sx, sy, ans[405][405];
int dir[8][2] = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
int main(){
    cin >> n >> m >> sx >> sy;
    queue<node> que;
    que.push((node){sx, sy, 0});
    ans[sx][sy] = -1;
    while (!que.empty()){
        node temp = que.front();
        que.pop();
        for (int i=0; i<8; ++i){
            int x =temp.x + dir[i][0];
            int y = temp.y +dir[i][1];
            if (x<1 || y < 1 || x>n || y > m || ans[x][y] != 0){
                continue;
            }
            ans[x][y] = temp.step +1;
            que.push((node){x, y, ans[x][y]});
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (j!=1) cout << ' ';
            if (ans[i][j] == -1){
                cout << 0;
            }else if (ans[i][j] == 0){
                cout << -1;
            }else{
                cout << ans[i][j];
            }
        }
        cout << endl;
    }
    return 0;
}

将ans数组赋初值为-1,减少特判

/*************************************************************************
    > File Name: 398.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 11 May 2021 08:34:28 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x, y, step;
};
int n, m, sx, sy, ans[405][405];
int dir[8][2] = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
int main(){
    cin >> n >> m >> sx >> sy;
    memset(ans, -1, sizeof(ans));
    queue<node> que;
    que.push((node){sx, sy, 0});
    ans[sx][sy] = 0;
    while (!que.empty()){
        node temp = que.front();
        que.pop();
        for (int i=0; i<8; ++i){
            int x =temp.x + dir[i][0];
            int y = temp.y +dir[i][1];
            if (x<1 || y < 1 || x>n || y > m || ans[x][y] != -1){
                continue;
            }
            ans[x][y] = temp.step +1;
            que.push((node){x, y, ans[x][y]});
        }
    }
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (j!=1) cout << ' ';
            cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

OJ-401 奇怪的象棋游戏升级版(作业)

OJ-303 矩阵距离一(作业)

OJ-305 乳草的入侵(作业)

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。