fork download
  1. // O(RC) BFS
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. int main() {
  8. int R,C;
  9. char c;
  10. scanf(" %d %d\n",&R,&C);
  11. vector< vector<bool> > V(R); // volne policko
  12. vector< vector<int> > dist(R); // vzdialenost
  13. pair<int,int> zac,end;
  14. for(int i =0; i < R; i++) {
  15. V[i].resize(C,true);
  16. dist[i].resize(C,-1);
  17. for(int j =0; j < C; j++) {
  18. scanf("%c",&c);
  19. if(c == 'X') V[i][j] =false;
  20. if(c == 'T') {
  21. zac.first =i;
  22. zac.second =j;}
  23. if(c == 'M') {
  24. end.first =i;
  25. end.second =j;}}
  26. scanf("\n");}
  27. int dx[4] ={1,-1,0,0};
  28. int dy[4] ={0,0,1,-1};
  29. queue< pair<int,int> > n;
  30. n.push(zac);
  31. dist[zac.first][zac.second] =0;
  32. while(!n.empty()) {
  33. if(n.front() == end) break;
  34. for(int i =0; i < 4; i++)
  35. if(V[n.front().first+dx[i]][n.front().second+dy[i]] && dist[n.front().first+dx[i]][n.front().second+dy[i]] == -1) {
  36. dist[n.front().first+dx[i]][n.front().second+dy[i]] =dist[n.front().first][n.front().second]+1;
  37. zac.first =n.front().first+dx[i];
  38. zac.second =n.front().second+dy[i];
  39. n.push(zac);}
  40. n.pop();}
  41. printf("%d\n",dist[end.first][end.second]);
  42. return 0;}
Success #stdin #stdout 0s 2972KB
stdin
20 51
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X..................X..............................X
X........X.......T.X....XXXXXXXXXXXXXXXXXXXXXX....X
X.XXXXXXXXXXXXXXXXXX....X....................X....X
X..................X....X....XXXXXXXXXXXX....X....X
X..................X....X....X..........XX.XXX....X
XXXXXXXXXXXXXXXXX..X....X....X....................X
X..................X....X....XXXXXXXXXXXXXXXXXXXXXX
X.......XXXXXXXXXXXXXXX.X....................X....X
X..................X....X..XXXXXXXXXXXXXXXXXXXXXXXX
X..................X....X.........................X
X..................X....XXXXXXXXXXXXXXXXXXXXXX....X
X.XXXXXXXXXXXXXXXXXX.XXXX....................X....X
X..................X....X....XXXXXXXXXXXX....X....X
X..................X....X....X..M.......XX...X....X
XXXXXXXXXXXXXXXXX..X....X....X...............X....X
X..................X....X....XXXXXXXXXXXXXXXXXXXX.X
X.......XXXXXXXXXXXXXXX.X....................X....X
X.......................X.........................X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
stdout
275