bfs搜索测试用例7错2

Question

bfs搜索测试用例7错2，题目如下：给定一个N*M方格的迷宫G，G中障碍物为0，道路为1，入口为（x1，y11），出口为（x2，y2），请问最少要走几个格子？

看看bfs哪里可能出错

#include <iostream>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,m,x1,x2,y11,y2;
const int N=200;
int map1[N][N]={0};
int pd[N][N]={0};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
typedef pair<int,int> PII;
int sum=0;
int bfs(int x,int y)
{
  queue<PII> q;
  q.push((PII){x,y});
  pd[x][y]=1;
  
  while(!q.empty())
  {
    int tx=q.front().first,ty=q.front().second;
    q.pop();
    for(int i=0;i<4;i++)
    {
      int xx=tx+dx[i],yy=ty+dy[i];
      if(xx<1||yy<1||xx>n||yy>m)continue;
      if(map1[xx][yy]==0||pd[xx][yy]>1)       continue;
      map1[xx][yy]=1;
      q.push((PII){xx,yy});      
      pd[xx][yy]=pd[tx][ty]+1;
      if(xx==x2&&yy==y2) return pd[xx][yy]-1;
    }
  }
}

int main()
{
  int s;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  cin>>map1[i][j];
  cin>>x1>>y11>>x2>>y2;
  s=bfs(x1,y11);
  cout<<s;
  // 请在此输入您的代码
  return 0;
}

Answer 1

参考GPT和自己的思路：可能存在以下问题：

1. 出口的判断条件应该在队列中弹出当前节点之后，否则会把出口先入队，但由于队列的特性，可能先弹出其他节点，导致出口未被判断直接结束循环，返回错误的结果。

修正方法：将出口的判断条件放在弹出当前节点之后。

1. pd数组初始化为0，但之后进行pd数组的判断时，如果pd[xx][yy] > 1，也会被认为是已经走过的节点，可能会出现错误。

修正方法：将pd数组初始化为-1，已走过的节点为1，未走过的节点为-1。

1. 在节点加入队列时，将其标记为已经走过，但是此时还没有弹出队列中的节点，如果有其他节点在此之前到达了同一个点并且步数更小，那么这个点在之后的遍历中还会继续被遍历，导致结果不正确。

修正方法：将节点入队和标记为已经走过的操作放在队列弹出当前节点之后。

经过以上修正，代码可以改为：

#include <iostream>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,m,x1,x2,y11,y2;
const int N=200;
int map1[N][N]={0};
int pd[N][N]={-1}; //修正
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
typedef pair<int,int> PII;
int sum=0;
int bfs(int x,int y)
{
  queue<PII> q;
  q.push((PII){x,y});
  pd[x][y]=1;
  
  while(!q.empty())
  {
    int tx=q.front().first,ty=q.front().second;
    q.pop();
    if(tx==x2 && ty==y2) return pd[tx][ty]-1; //修正
    for(int i=0;i<4;i++)
    {
      int xx=tx+dx[i],yy=ty+dy[i];
      if(xx<1||yy<1||xx>n||yy>m)continue;
      if(map1[xx][yy]==0||pd[xx][yy]!=-1) continue; //修正
      q.push((PII){xx,yy});
      pd[xx][yy]=pd[tx][ty]+1;
    }
  }
  return -1; //修正
}

int main()
{
  int s;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  cin>>map1[i][j];
  cin>>x1>>y11>>x2>>y2;
  s=bfs(x1,y11);
  cout<<s;
  // 请在此输入您的代码
  return 0;
}