Advertisement
Guest User

Untitled

a guest
Jun 24th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. struct Pos{
  9.  
  10. int i;
  11.  
  12. int j;
  13.  
  14. };
  15.  
  16. bool operator !=(Pos a, Pos b){
  17. return !(a.i == b.i && a.j == b.j);
  18. }
  19.  
  20. int main(){
  21. freopen("input.txt", "r", stdin);
  22. freopen("output.txt", "w", stdout);
  23. int n, m;
  24. cin>>n>>m;
  25. vector<Pos > teleport;
  26. vector<vector<char> > g(n, vector<char>(m));
  27. vector<vector<int> > d(n, vector<int>(m, 1e7));
  28. for(int i = 0; i < n; i++){
  29. for(int j = 0; j < m; j++){
  30. cin>>g[i][j];
  31. if(g[i][j] == 'T'){
  32. teleport.push_back(Pos{i, j});
  33. }
  34. }
  35. }
  36. int x1, y1, x2, y2;
  37. cin>>x1>>y1>>x2>>y2;
  38.  
  39. x1--;y1--;x2--;y2--;
  40. queue<Pos> q;
  41. q.push(Pos{x1, y1});
  42. d[x1][y1] = 0;
  43. while(true){
  44. Pos v = q.front();
  45. q.pop();
  46.  
  47. for(int di = -1; di <= 1; di++){
  48. for(int dj = -1; dj <= 1; dj++){
  49. if(di * di + dj * dj == 1){
  50. int ni = v.i + di;
  51. int nj = v.j + dj;
  52. if(ni >= 0 && ni < n && nj >= 0 && nj < m && d[ni][nj] > d[v.i][v.j]){
  53. q.push(Pos{ni, nj});
  54. d[ni][nj] = d[v.i][v.j] + 1;
  55. }
  56. }
  57. }
  58. }
  59.  
  60. if(g[v.i][v.j] == 'T'){
  61. for(auto i : teleport){
  62. if(d[i.i][i.j] > d[v.i][v.j]){
  63. q.push(i);
  64. d[i.i][i.j] = d[v.i][v.j];
  65. }
  66. }
  67. }
  68. if(d[x2][y2] != 1e7){
  69. cout<<d[x2][y2];
  70. return 0;
  71. }
  72. }
  73.  
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement