m0_69114617 2023-03-26 18:28 采纳率: 60%
浏览 17
已结题

bfs搜索测试用例7错2

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;
}
  • 写回答

1条回答 默认 最新

  • IT_service_mesh 2023-03-26 18:45
    关注

    参考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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 4月3日
  • 已采纳回答 3月26日
  • 创建了问题 3月26日

悬赏问题

  • ¥15 C#字典调用时报错,有关文件加载
  • ¥100 在连接内网VPN时,如何同时保持互联网连接
  • ¥15 MATLAB中使用parfor,矩阵Removal的有效索引在parfor循环中受限制
  • ¥20 Win 10 LTSC 1809版本如何无损提升到20H1版本
  • ¥50 win10 LTSC 虚拟键盘不弹出
  • ¥30 关于PHP中POST获取数据的问题
  • ¥30 微信小程序请求失败,网页能正常带锁访问
  • ¥15 Python实现hog特征图可视化
  • ¥30 德飞莱51单片机实现C4炸弹
  • ¥50 CrossLink-LIF-MD6000 型 FPGA 的 CMOS 转 MIPI D-PHY IP 核功能使用异常