Information
- ID
- 770
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 6
- Tags
- # Submissions
- 191
- Accepted
- 53
- Uploaded By
#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;
int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
struct temp {
int x,y,step;
};
queue<temp> q;
char a[105][105];
int vis[105][105];
void bfs(int xx,int yy) {
while(!q.empty()) {
temp k=q.front();
if(a[k.x][k.y]=='T') {
cout<<k.step<<endl;
return ;
}
q.pop();
if(vis[k.x][k.y])
continue;
vis[k.x][k.y]=1;
for(int i=0; i<4; i++) {
int tx=k.x+dx[i],ty=k.y+dy[i];
if(tx>=0&&ty>=0&&tx<n&&ty<m&&!vis[tx][ty]&&a[tx][ty]!='#') {
q.push({tx,ty,k.step+1});
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++) {
cin>>a[i];
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(a[i][j]=='S') {
q.push({i,j,0});
bfs(i,j);
return 0;
}
}
}
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.