Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.84 KB | None | 0 0
  1. #include<fstream>
  2. #include<queue>
  3. #include<stack>
  4. #include<vector>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10. fstream fin("maze.in");
  11. ofstream fout("maze.out");
  12.  
  13. int N, M;
  14. int X1, X2, Y1, Y2;
  15.  
  16. fin >> N >> M;
  17. fin >> X1 >> Y1;
  18. fin >> X2 >> Y2;
  19.  
  20. if (X1==X2 && Y1==Y2)
  21. {
  22. fout << "0" << endl;
  23. fout << X1 << " " << Y1;
  24. return 0;
  25. }
  26.  
  27. X1--; X2--; Y1--; Y2--;
  28.  
  29. vector < vector < int>> labirint(N, vector<int>(M));
  30.  
  31.  
  32. for (int i = 0; i < N; i++)
  33. {
  34. for (int j = 0; j < M; j++)
  35. {
  36. fin >> labirint[i][j];
  37. }
  38. }
  39.  
  40.  
  41. vector < vector < int>> cells_visited(N, vector<int>(M));
  42.  
  43.  
  44. cells_visited[X1][Y1] = 1;
  45.  
  46.  
  47. vector<vector<pair<int, int>>>
  48. way(N, vector < pair<int, int>>
  49. (M, make_pair(-1, -1)));
  50.  
  51. queue<pair<int, int>>queue;
  52. queue.push(make_pair (X1, Y1));
  53.  
  54. while (!queue.empty())
  55. {
  56. int value1 = queue.front().first;
  57. int value2 = queue.front().second;
  58.  
  59. queue.pop();
  60.  
  61.  
  62. if (value1+1 < N)
  63. {
  64. if (labirint[value1+1][value2]!=0)
  65. {
  66. if (!cells_visited[value1 + 1][value2])
  67. {
  68. cells_visited[value1 + 1][value2] = 1;
  69. way[value1 + 1][value2] = make_pair(value1 , value2);
  70. queue.push(make_pair(value1 + 1, value2));
  71. }
  72. }
  73. }
  74.  
  75. if (value2 + 1 < M)
  76. {
  77. if (labirint[value1][value2+1] != 0)
  78. {
  79. if (!cells_visited[value1][value2+1])
  80. {
  81. cells_visited[value1][value2+1] = 1;
  82. way[value1][value2+1] = make_pair(value1, value2);
  83. queue.push(make_pair(value1, value2+1));
  84. }
  85. }
  86. }
  87.  
  88. if (value1 - 1 >= 0)
  89. {
  90. if (labirint[value1-1][value2] != 0)
  91. {
  92. if (!cells_visited[value1 -1][value2])
  93. {
  94. cells_visited[value1 - 1][value2] = 1;
  95. way[value1 - 1][value2] = make_pair(value1, value2);
  96. queue.push(make_pair(value1 - 1, value2));
  97. }
  98. }
  99. }
  100.  
  101. if (value2 - 1 >= 0)
  102. {
  103. if (labirint[value1][value2-1] != 0)
  104. {
  105. if (!cells_visited[value1][value2-1])
  106. {
  107. cells_visited[value1][value2-1] = 1;
  108. way[value1][value2-1] = make_pair(value1, value2);
  109. queue.push(make_pair(value1, value2-1));
  110. }
  111. }
  112. }
  113.  
  114. }
  115.  
  116. if (way[X2][Y2].first == -1)
  117. {
  118. fout << "-1"<<endl;
  119. }
  120. else
  121. {
  122. stack<pair<int, int>> final_way;
  123.  
  124. for (int valueX2 = X2, valueY2 = Y2; ; )
  125. {
  126. if (valueX2 == X1 && valueY2 == Y1)
  127. {
  128. break;
  129.  
  130. }
  131.  
  132. final_way.push(make_pair(valueX2 + 1, valueY2 + 1));
  133. int variable = valueX2;
  134. valueX2 = way[valueX2][valueY2].first;
  135. valueY2 = way[variable][valueY2].second;
  136.  
  137. }
  138.  
  139. final_way.push(make_pair(X1 + 1, Y1 + 1));
  140. int way_size = final_way.size();
  141. fout << way_size - 1 << endl;
  142.  
  143. while (!final_way.empty())
  144. {
  145. fout << final_way.top().first << " " << final_way.top().second << endl;
  146. final_way.pop();
  147. }
  148. }
  149.  
  150.  
  151. fin.close();
  152. fout.close();
  153. return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement