1 solutions
-
0
C++ :
#include<bits/stdc++.h> #define R register #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 26 #define MOD 2520 #define E 1e-12 using namespace std; int r,c; char a[N][N]; bool vis[N][N]; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct node{ int x; int y; int step; }q[N*100]; template <typename T> void read(T &t){ t=0; char ch=getchar(); int f=1; while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } do{ (t*=10)+=ch-'0'; ch=getchar(); }while(ch>='0'&&ch<='9'); t*=f; } void bfs(int sx,int sy,int ex,int ey){ int head=1,tail=1; bool flag=true; memset(vis,0,sizeof(vis)); vis[sx][sy]=1; q[tail].x=sx; q[tail].y=sy; q[tail].step=0; tail++; while(head<tail){ int x=q[head].x; int y=q[head].y; int step=q[head].step; if(x==ex&&y==ey){ flag=false; printf("%d\n",step); break; } for(int i=0;i<4;i++){ int nx=x+dir[i][0]; int ny=y+dir[i][1]; if(nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]==0&&a[nx][ny]=='.'){ vis[nx][ny]=1; q[tail].x=nx; q[tail].y=ny; q[tail].step=step+1; tail++; } } head++; } if(flag) printf("-1\n"); } int main(){ int sx,sy,ex,ey; cin>>r>>c; for(int i=0;i<r;i++) scanf("%s",a[i]); for(int i=0;i<r;i++) for(int j=0;j<c;j++){ if(a[i][j]=='@'){ sx=i; sy=j; } if(a[i][j]=='*'){ ex=i; ey=j; a[i][j]='.'; } } bfs(sx,sy,ex,ey); return 0; }
- 1
Information
- ID
- 9942
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By