[已解决]关于BFS搜索求助，完全看不出问题

额外减小

rt.洛谷没人回答我，那我只好上这问了。

题目链接：https://www.luogu.com.cn/problem/P1746

问题：https://www.luogu.com.cn/discuss/689287

code:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef struct
{
        int x;
        int y;
        int step;
}point;

int main()
{
        
        int n,mp[1145][1145],x1,y1,x2,y2,ch,bx[]={-1,0,0,1},by[]={0,1,-1,0};
        bool road[1145][1145]={};
        scanf("%d",&n);
        getchar();
        for(int i=0;i<=n;i++)
        {
                for(int j=0;j<=n;j++)
                {
                        mp[i][j]=-1;
                }
        }
        for(int i=1;i<=n;i++)
        {
                
                for(int j=1;j<=n;j++)
                {
                        ch=getchar();
                        if(ch=='0')road[i][j]=true;//okay.
            //putchar(ch);
                }
                getchar();
        //putchar('\n');
        }
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        queue<point> q;
        q.push((point){x1,y1,0});
        while(!(q.empty()))
        {
                for(int i=0;i<4;i++)
                {
                        if(road[q.front().x+bx[i]][q.front().y+by[i]] and mp[q.front().x+bx[i]][q.front().y+by[i]]==-1)
                        {
                                //putchar('-');
                                mp[q.front().x+bx[i]][q.front().y+by[i]]=q.front().step+1;
                //printf("++%d %d++",q.front().x,q.front().y);
                                q.push((point){q.front().x+bx[i],q.front().y+by[i],q.front().step+1});
                        }
                }
                q.pop();
        }
        printf("%d\n",mp[x2][y2]);
        
}

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2023-9-23 11:17:51

你代码风格有点...
我自己写了以下, 过了, 你自己看下呢
写代码不要写特别繁琐 , 不然看不出来的

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

const int N = 1314;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

struct Step{
    int x, y, step;
};

bitset<N> mp[N];  // 地图
bitset<N> vis[N];

int n, X1, X2, Y1, Y2;
char ch;
queue<Step> q;

bool check(int x, int y){
    return (x > 0 && x <= n && y > 0 && y <= n && !mp[x][y] && !vis[x][y]);
}

int bfs(){
    q.push({X1, Y1, 0});
    vis[X1][Y1] = 1;

    while(!q.empty()){
        auto cur = q.front();
        q.pop();

        if(cur.x == X2 && cur.y == Y2){
            return cur.step;
        }

        for(int i = 0; i < 4; i++){
            auto px = cur.x + dx[i];
            auto py = cur.y + dy[i];

            if(check(px, py)){
                vis[px][py] = 1;
                q.push({px, py, cur.step + 1});
            }
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> ch;
            if(ch == '1') mp[i][j] = 1;
        }
    }
    cin >> X1 >> Y1 >> X2 >> Y2;

    cout << bfs();

    return 0;
}

跳转到最佳答案楼层

isdkz

这段代码实现的是一个BFS搜索算法，用于在一个n x n的01矩阵中，求从(x1, y1)到(x2, y2)的最短路径长度。

代码中使用了一个结构体point，用于存储每个点的坐标和步数。在搜索过程中，从队首取出一个点，遍历它的四个相邻点，如果该相邻点是通路且没有被搜索过，则将该点加入队列，并更新该点的步数。

在代码中，mp数组用于存储每个点到起点的最短路径长度，初始值为-1，表示该点没有被搜索过。road数组用于存储01矩阵中每个点是否为通路，初始值为false，表示该点不是通路。

代码实现上看起来没有问题，但是可能存在以下几个问题：

1. 代码中没有对输入数据进行有效性检查，如输入的n是否合法，起点和终点是否在矩阵范围内等。

2. 在读入01矩阵时，代码中使用了getchar()函数，但是没有判断输入是否合法，可能会导致程序出错。

3. 在搜索过程中，如果起点和终点不连通，则mp数组中终点的值仍为-1，需要在输出结果前判断终点是否被搜索过。

建议在代码中添加有效性检查和错误处理，以及在输出结果前判断终点是否被搜索过。

sfqxx

一个内存溢出了吧

柿子饼同学

你代码风格有点...
我自己写了以下, 过了, 你自己看下呢
写代码不要写特别繁琐 , 不然看不出来的

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

const int N = 1314;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

struct Step{
    int x, y, step;
};

bitset<N> mp[N];  // 地图
bitset<N> vis[N];

int n, X1, X2, Y1, Y2;
char ch;
queue<Step> q;

bool check(int x, int y){
    return (x > 0 && x <= n && y > 0 && y <= n && !mp[x][y] && !vis[x][y]);
}

int bfs(){
    q.push({X1, Y1, 0});
    vis[X1][Y1] = 1;

    while(!q.empty()){
        auto cur = q.front();
        q.pop();

        if(cur.x == X2 && cur.y == Y2){
            return cur.step;
        }

        for(int i = 0; i < 4; i++){
            auto px = cur.x + dx[i];
            auto py = cur.y + dy[i];

            if(check(px, py)){
                vis[px][py] = 1;
                q.push({px, py, cur.step + 1});
            }
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> ch;
            if(ch == '1') mp[i][j] = 1;
        }
    }
    cin >> X1 >> Y1 >> X2 >> Y2;

    cout << bfs();

    return 0;
}

额外减小

柿子饼同学 发表于 2023-9-23 11:17
你代码风格有点...
我自己写了以下, 过了, 你自己看下呢
写代码不要写特别繁琐 , 不然看不出来的

呵呵。原来我是字符操作的问题。
用 getchar() 吃换行符已经寄了无数次了
还是谢谢你