3 solutions
-
0
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> #include <string.h> #include <queue> #include <stack> #include <map> #include <set> #include <vector> using namespace std; int n,m; char a[45][45]; int vis[45][45]; struct temp { int tx; int ty; int step; }; int nx[4]= {0,0,1,-1}; int ny[4]= {1,-1,0,0}; queue<temp> q; void bfs() { while(!q.empty()) { temp t=q.front(); q.pop(); if(t.tx==n-1&&t.ty==m-1) { cout<<t.step; return; } if(vis[t.tx][t.ty]) continue; vis[t.tx][t.ty]=1; for(int i=0; i<4; i++) { int x=t.tx+nx[i],y=t.ty+ny[i]; if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==0&&a[x][y]=='.') q.push({x,y,t.step+1}); } } } int main() { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { cin>>a[i]; } q.push({0,0,1}); bfs(); return 0; }
Information
- ID
- 769
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 7
- Tags
- # Submissions
- 445
- Accepted
- 88
- Uploaded By