0分BFS求调！！！

RedDog @ 2023-08-20 14:39:41

#include <iostream>
#include <cstring>
using namespace std;
long long ans;
int n,m;
int ma[100][100],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char ch;
int x,y;
bool found=false,vis[100][100];
void bfs();
int main(){
    ios::sync_with_stdio(false);
    memset(vis,false,sizeof(vis));
    cin >> n >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin >> ch;
            if(ch == '.') ma[n][m] = 1;
            else ma[m][n] = 0;
        }
    int a[100000000][2];
    memset(a,0,sizeof(a));
    int head=0,rear=1;
    do{
        head++;
        for(int k=0;k<4;++k){
            x += dx[k];y += dy[k];
            if(x==m&&y==n){found = true;rear=head;break;}
            if(x<m&&x>=0&&y<n&&y>=0&&ma[x][y]==1){
                rear++;
                a[rear][0] = x+dx[k];
                a[rear][1] = y+dy[k];
                ma[x][y] = 0;
            }
        }
    }while(head<rear);
    if(found) cout <<"Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

by liu_le_chen @ 2023-08-20 14:50:35

也是广搜，你看一下，我慢慢帮你检查

#include<bits/stdc++.h>
using namespace std;
long long n,m,f,flag[1001][1001],vis[4][2]={-1,0,1,0,0,-1,0,1};
char arr[1001][1001];
struct node{
    int x,y;
};
queue<node> q;
void bfs(){
    q.push({1,1});
    flag[1][1]=1;
    while(!q.empty()){
        for(int i=0;i<4;i++){
            int xx=q.front().x+vis[i][0];
            int yy=q.front().y+vis[i][1];
            if(arr[xx][yy]=='.' && flag[xx][yy]==0 && xx>=1 && xx<=n && yy>=1 && yy<=m){
                flag[xx][yy]=1;
                if(xx==n && yy==m){
                    cout<<"Yes";
                    f=0;
                    return;
                }
                q.push({xx,yy});
            }
        }
        q.pop();
    }
}
int main(){
    f=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
        }
    }
    bfs();
    if(f) cout<<"No";
    return 0;
}

@RedDog

by liu_le_chen @ 2023-08-20 14:51:21

样例过了吗@RedDog

by RedDog @ 2023-08-20 14:59:23

@liulechen 看过了，谢谢。

by liu_le_chen @ 2023-08-20 15:01:06

@RedDog 建议用队列去实现广搜，更加清晰，还有，你稍微加一点注释吧

by RedDog @ 2023-08-21 11:34:43

发错了，再发一次。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct Node{
    int x,y;
};
queue<Node> q;
int x,y,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},m,n;
char maze[1001][1001],ch;
bool found = false;
void bfs();
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin >> maze[i][j];
        }
    bfs();
    if(found) cout <<"Yes" << endl;
    else cout << "No" << endl;
    return 0;
}
void bfs(){
    q.push({0,0});
    maze[0][0] = 0;
    while(q.empty()){
        for(int i=0;i<4;i++){
            int xx = q.front().x+dx[i];
            int yy = q.front().y+dy[i];
            if(xx<m&&xx>=0&&yy<n&&yy>=0&&maze[xx][yy]=='.'){
                q.push({xx,yy});
                maze[xx][yy] = 0;
                if(xx==m-1&&yy==n-1){
                    found = true;
                    return;
                }
            }
        }
        q.pop();
    }
}

by RedDog @ 2023-08-22 11:08:02

这个还是不行。。。

by RedDog @ 2023-08-22 11:26:41

终于AC了，谢谢。