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

额外减小 · 发表于 2023-9-22 23:32:37

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

本帖最后由柿子饼同学于 2023-9-23 11:20 编辑

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

#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 · 发表于 2023-9-22 23:32:48

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

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

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

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

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

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

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

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

sfqxx · 发表于 2023-9-23 09:29:26

一个内存溢出了吧

柿子饼同学 · 发表于 2023-9-23 11:17:51

本帖最后由柿子饼同学于 2023-9-23 11:20 编辑

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

#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 13:54:48

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

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

还是谢谢你

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块