我们只需要 bfs,找到所有可能的路径,判断一下就行了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=57;
int n,m,a[N][N];
bool vis[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
struct node{
int x,y;
};
queue<node>q;
void solve(){
//start
cin.tie(0)->ios::sync_with_stdio(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cin>>a[i][j];
}
q.push({1,1});
vis[1][1]=1;
while(q.size()){
auto u=q.front();
q.pop();
if(u.x==n&&u.y==m){
cout<<"Yes";
return;
}
for(int i=0;i<4;i++){
int tx=u.x+dx[i],ty=u.y+dy[i];
if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]||a[tx][ty])continue;
vis[tx][ty]=1;
q.push({tx,ty});
}
}
cout<<"No";
}
signed main(){
solve();
return 0;
}
暂无评论