救救孩子，BFS 80昏

BaiBaiShaFeng @ 2024-11-26 17:22:18

#include <bits/stdc++.h>
using namespace std;
int n, m;
char ma[114][114];
bool f=false;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct Point{
    int x, y;
};
bool vis[114][114];
deque <Point> q;
void bfs(int px, int py){
    Point st;
    st.x=px;
    st.y=py;
    vis[px][py]=1;
    q.push_back(st);
    while(!q.empty()){
        Point nw=q.front();
        if(nw.x==m&&nw.y==n){
            f=true;
        }
        for(int i=1; i<=3; i++){
            Point next=nw;
            next.x+=dx[i];next.y+=dy[i];    
            if(ma[next.x][next.y]=='#'||vis[next.x][next.y]==1){
                continue;
            }
            vis[next.x][next.y]==1;
        }
        q.pop_front();
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0; i<=110; i++){for(int j=0; j<=110; j++){ma[i][j]='#';}}
    for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){scanf("%c",&ma[j][i]);}}
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(ma[j][i]=='.'&&vis[j][i]!=true){
                bfs(j,i);
            }
        }
    }
    if(f==true){
        cout<<"Yes";return 0;
    }
    cout<<"No";
    return 0;
}

by qujunhao @ 2024-11-26 17:41:00

#include<bits/stdc++.h>
using namespace std;
struct node{
    int nx,ny;
};
queue<node>q;
int vis[105][105];
char maze [105][105];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m;
void bfs(int x,int y){
    node a;
    a.nx=x;
    a.ny=y;
    q.push(a);
    vis[x][y]=1;
    while(!q.empty()){
        node b=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int dx=b.nx+dir[i][0];
            int dy=b.ny+dir[i][1];
            if(dx>0&&dx<=n&&dy>0&&dy<=m&&vis[dx][dy]==0&&maze[dx][dy]=='.'){
                vis[dx][dy]=1;
                if(dx==n&&dy==m){
                    cout<<"Yes"<<endl;
                    return;
                }
                a.nx=dx;
                a.ny=dy;
                q.push(a);
            }
        }
    }
    cout<<"No"<<endl;
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>maze[i][j];
        }
    }
    bfs(1,1);
    return 0;//我也是，代码给你
}

by qujunhao @ 2024-11-26 17:41:09

@baibaishafeng123

by qujunhao @ 2024-11-26 17:42:06

个人觉得不用双端队列，求关

by fire_hua @ 2024-11-26 17:42:36

        for(int i=1; i<=3; i++){

把i变成从0开始行吗？

by YBa2Cu3O7 @ 2024-11-26 17:48:25

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> G(n,vector<int>(m,0));
    auto tr=G;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            char ch;
            cin>>ch;
            G[i][j]=ch=='#'?1:0;
        }
    }
    int ans=0;
    const array<int,4> mvx{0,0,1,-1};
    const array<int,4> mvy{1,-1,0,0};
    auto check=[&](int x,int y){
        return x>=0&&x<n&&y>=0&&y<m&&tr[x][y]==0&&G[x][y]==0;
    };
    queue<pair<int,int>> q;
    q.push({0,0});
    tr[0][0]=1;
    while(!q.empty()){
        int sz=q.size();
        for(int i=0;i<sz;++i){
            const auto& p=q.front();
            for(int j=0;j<4;++j){
                auto x=p.first+mvx[j],y=p.second+mvy[j];
                if(check(x,y)){
                    q.push({x,y});
                    tr[x][y]=1;
                }
            }
            q.pop();
        }
        if(tr[n-1][m-1]==1){
            ans=1;
            break;
        }
    }
    cout << (ans ? "Yes" : "No");
}

by BaiBaiShaFeng @ 2024-11-26 18:02:49

@qujunhao 感谢大佬已关

by Bloom0117 @ 2024-11-27 00:08:21

@YBa2Cu3O7好的喵