1 条题解
-
1
陈海斌 (阳光少年chen) LV 8 @ 2023-8-25 14:54:44
dfs版:
#include <iostream> #include <cstring> using namespace std; struct point{ int x,y; }; point s,t; int n; char a[110][110]; bool vis[110][110]; bool flag=false; int d[][2]={{-1,0},{1,0},{0,-1},{0,1}}; void dfs(point p){ if(p.x==t.x&&p.y==t.y){ flag=true; return; } for(int i=0;i<4;i++){ point nxt; nxt.x=p.x+d[i][0]; nxt.y=p.y+d[i][1]; if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>n)continue; if(a[nxt.x][nxt.y]=='.'&&!vis[nxt.x][nxt.y]){ vis[nxt.x][nxt.y]=1; dfs(nxt); } } } int main(){ int T; cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } cin>>s.x>>s.y>>t.x>>t.y; s.x++;s.y++;t.x++;t.y++; flag=false; memset(vis,0,sizeof vis); vis[s.x][s.y]=1; dfs(s); if(flag)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
bfs版:
#include <iostream> #include <cstring> #include <queue> using namespace std; struct point{ int x,y; }; point s,t; int n; char a[110][110]; bool vis[110][110]; bool flag=false; int d[][2]={{-1,0},{1,0},{0,-1},{0,1}}; void bfs(point s){ queue<point>q; q.push(s); vis[s.x][s.y]=1; while(!q.empty()){ point p=q.front(); q.pop(); if(p.x==t.x&&p.y==t.y){ flag=true; return; } for(int i=0;i<4;i++){ point nxt; nxt.x=p.x+d[i][0]; nxt.y=p.y+d[i][1]; if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>n)continue; if(a[nxt.x][nxt.y]=='.'&&!vis[nxt.x][nxt.y]){ vis[nxt.x][nxt.y]=1; q.push(nxt); } } } } int main(){ int T; cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } cin>>s.x>>s.y>>t.x>>t.y; s.x++;s.y++;t.x++;t.y++; flag=false; memset(vis,0,sizeof vis); vis[s.x][s.y]=1; bfs(s); if(flag)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
- 1
信息
- ID
- 3023
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 42
- 已通过
- 18
- 上传者