2 条题解
-
1陈海斌 (阳光少年chen) LV 9 @ 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; }
-
02024-7-19 11:47:22@
#include<iostream> #include<cstring> using namespace std; const int N=1e3+520; int n,t,sx,sy,ex,ey; char a[N][N]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; bool flag; bool check(int x,int y){ if(x>=0&&x<n&&y>=0&&y<n&&a[x][y]=='.') return 1; return 0; } void dfs(int x,int y){ if(x==ex&&y==ey){ flag=1; return ; } for(int i=0;i<=3;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(check(xx,yy)){ a[xx][yy]='#'; dfs(xx,yy); } } } int main(){ cin>>t; while(t--){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } } cin>>sx>>sy>>ex>>ey; dfs(sx,sy); if(flag){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } flag=0; } return 0; }
- 1
信息
- ID
- 3023
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 48
- 已通过
- 23
- 上传者