bfs求调

yuanshen362 @ 2024-08-29 15:12:57

#include<bits/stdc++.h>
using namespace std;
int n,m,f;
char c[2005][2005];
bool vis[2005][2005];
struct node{
    int x,y;
};
int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
void bfs()
{
    queue<node>q;
    q.push({1,1});
    while(!q.empty())
    {
        while(vis[q.front().x][q.front().y])q.pop();
        if(q.empty())return;
        int x=q.front().x,y=q.front().y;
        q.pop();
        vis[x][y]=1;
        for(int i=1;i<=4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(c[tx][ty]=='.')q.push({tx,ty});
            if(tx==n&&ty==m){
                f=1;
                return;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        cin>>c[i][j];
    }
    bfs();
    if(f)cout<<"Yes";
    else cout<<"No";
    return 0;
}

by DHT666 @ 2024-08-29 15:26:02

第 16 行，使用队列时要判空，应加上队列不为空的条件。

#include<bits/stdc++.h>
using namespace std;
int n,m,f;
char c[2005][2005];
bool vis[2005][2005];
struct node{
    int x,y;
};
int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
void bfs()
{
    queue<node>q;
    q.push({1,1});
    while(!q.empty())
    {
        while(!q.empty()&&vis[q.front().x][q.front().y])q.pop();
        if(q.empty())return;
        int x=q.front().x,y=q.front().y;
        q.pop();
        vis[x][y]=1;
        for(int i=1;i<=4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(c[tx][ty]=='.')q.push({tx,ty});
            if(tx==n&&ty==m){
                f=1;
                return;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        cin>>c[i][j];
    }
    bfs();
    if(f)cout<<"Yes";
    else cout<<"No";
    return 0;
}

by wdnmd9028 @ 2024-08-29 15:26:46

边界情况没考虑