C++ bfs 不知道具体哪里出问题了

Nemo_ @ 2023-07-11 14:32:37

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[105][105];
struct search1
{
    int x,y;
}; 
queue<search1>a;
int xx[5]={0,0,1,-1};
int yy[5]={1,-1,0,0};
int main()
{
    cin>>n>>m;
    search1 tmp;
    int xa=1,xb=1;
    tmp.x=xa; tmp.y=xb;
    a.push(tmp);//起始位置入队 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[n][m];
        }
    }
    while(!a.empty())
    {
        search1 now=a.front();
        a.pop();
        if(now.x==n&&now.y==m)//判断位置 
        {
            cout<<"Yes";
            return 0;
        }
        for(int i=0;i<4;i++)
        {
            int ax=now.x+xx[i];
            int ay=now.y+yy[i];
            if(c[ax][ay]=='.'&&ax>=1&&ay>=1&&ax<=n&&ay<=m)
            {//合法 入队 (BUT 它合法但是不经过这里)
                tmp.x=ax;tmp.y=ay;
                a.push(tmp);
            }
            else
            {//非法 下一次循环 
                continue;
            }
        }
    }
    cout<<"No"<<endl;//如果队列为空且走不到（n,m） 
    return 0;
}

by Nemo_ @ 2023-07-11 14:33:15

输出全都是 No

by catandcode @ 2023-07-11 14:42:48

@Nemo_ 地图输入写成cin>>c[n][m]。

by KidzzZip @ 2023-07-11 14:46:07

@Nemo_ 输入写成cin>>c[n][m]了，应该写成cin>>c[i][j]。

by KidzzZip @ 2023-07-11 14:53:14

帮你改了一下，记得以后写BFS遍历点的时候加个Vis数组记录这个点有没有走过,不然会超时。

#include<bits/stdc++.h>
using namespace std;
int n,m,xx[5]={0,0,1,-1},yy[5]={1,-1,0,0};
char c[101][101];
bool vis[101][101];
struct node
{
    int x,y;
}; 
queue<node>a;
int main()
{
    cin>>n>>m;
    a.push((node){1,1});
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
        }
    }
    while(!a.empty())
    {
        node now=a.front();
        a.pop();
        if(now.x==n&&now.y==m)
        {
            cout<<"Yes";
            return 0;
        }
        for(int i=0;i<4;i++)
        {
            int ax=now.x+xx[i];
            int ay=now.y+yy[i];
            if(c[ax][ay]=='.'&&ax>=1&&ay>=1&&ax<=n&&ay<=m&&!vis[ax][ay])
            {
                vis[ax][ay]=true;
                a.push((node){ax,ay});
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

by Nemo_ @ 2023-07-11 15:32:10

谢谢dalao 如果这条路要走第二次， 那被vis标记过不久不能走了？

by Nemo_ @ 2023-07-11 15:32:28

@KidzzZip

by Nemo_ @ 2023-07-11 15:35:05

不带vis交了一下，全都MLE和TLE了，为啥啊

by KidzzZip @ 2023-07-11 16:12:45

因为到这个点已经最短，用vis标记过这个点的数值就不会改变。

不带Vis数组的话一些点会走很多次当然会TLE。

by Nemo_ @ 2023-07-11 16:19:44

@KidzzZip 懂啦，谢谢

by Nemo_ @ 2023-07-11 16:24:31

@catandcode 谢谢dalao