BFS40分求调！（悬关，先到先得）

Hope5365 @ 2023-10-20 19:27:10

#include <iostream>
#include <queue>
using namespace std;

const int N = 1e2 + 10;
bool mark[N][N],can[N][N];
int n,m,ans;

struct Bit
{
    int x,y;
};
queue <Bit> q;

void bfs()
{
    q.push({1,1});
    while (!q.empty())
    {
        Bit k = q.front();
        int x = k.x,y = k.y;
        q.pop();
        if (!can[x][y] || mark[x][y]) continue;
        if (x == n && y == m)
        {
            ans = 1;
            break;
        }
        mark[x][y] = 1;
        q.push({x + 1,y});
        q.push({x - 1,y});
        q.push({x,y + 1});
        q.push({x,y - 1});
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
        {
            char c;
            scanf("%c",&c);
            can[i][j] = (c == '.');
        }
    bfs();
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

by NO_OI_NO_LIFE @ 2023-10-20 19:30:38

判越界?

by yhx0322 @ 2023-10-20 19:32:37

没有判断数组下标越界的问题。

可能会访问到非法内存。

by yhx0322 @ 2023-10-20 19:33:00

@Hope5365

by dhwrthw @ 2023-10-20 19:48:24

这里

    q.push({x + 1,y});
    q.push({x - 1,y});
    q.push({x,y + 1});
    q.push({x,y - 1});

没有判断，会超过范围

还有

    if (!can[x][y] || mark[x][y]) continue;

应该在放入队列时判断，这样会添加很多重复的点

AC:

#include<bits/stdc++.h>
using namespace std;

const int N=105;
int n,m;
char a[N][N];

struct Node{
    int x,y;
};
int dirs[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
bool vis[N][N];
void bfs(){
    queue<Node> q;
    q.push({1,1});
    vis[1][1]=true;
    while(!q.empty()){
        Node node=q.front();q.pop();
        if(node.x==n&&node.y==m){
            printf("Yes");
            return;
        }
        for(int i=0;i<4;i++){
            int nx=node.x+dirs[i][0],ny=node.y+dirs[i][1];
            if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||a[nx][ny]=='#')continue;
            vis[nx][ny]=true;q.push({nx,ny});
        }
    }
    printf("No");
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        cin>>a[i][j];
    }
    bfs();
    return 0;
}

by NO_OI_NO_LIFE @ 2023-10-20 19:53:43

为了你我特意做了此题,一遍AC,因为是NOI Linux copy出来的,所以马蜂怪异,还请见谅

#include <bits/stdc++.h>
using namespace std;
int n,m;
char mp[105][105];
bool vis[105][105];

struct node{
        int x,y;
};

int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};

int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                        cin>>mp[i][j];

        queue<node> q;
        q.push((node){1,1});
        while(!q.empty()){
                node f=q.front();q.pop(); 
                int x=f.x,y=f.y;
                for(int i=1;i<=4;i++){
                        int nx=x+dx[i];
                        int ny=y+dy[i];
                        if(x<1||y<1||x>n||y>m||mp[nx][ny]=='#'||vis[nx][ny]) continue;
                        if(nx==n&&ny==m){
                                cout<<"Yes"<<endl;
                                return 0;
                        }
                        q.push((node){nx,ny});
                        vis[nx][ny]=true;
                }
        }
        cout<<"No"<<endl;
        return 0;
}/*                                                                                                                                                                                                                                                         
3 5 
.##.# 
.#... 
...#. 
*/

by Hope5365 @ 2023-10-21 18:07:40

@yhx0322 一关