Advertisement
Guest User

Untitled

a guest
May 26th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <fstream>
  4. #include <vector>
  5. #include <stack>
  6.  
  7. struct coord{
  8. unsigned int x, y;
  9. };
  10.  
  11. void check (std::vector<std::vector<coord>> &last, std::queue<coord> &qu, std::vector<std::vector<char>> &maze, int x, int y, coord &coordinate) {
  12. last[x][y] = coordinate;
  13. coord temp;
  14. temp.x = x;
  15. temp.y = y;
  16. qu.push(temp);
  17. maze[x][y] = '+';
  18. }
  19.  
  20. int main() {
  21. unsigned int n, x, y;
  22. coord start, finish, coordinate;
  23. std::vector<std::vector<char>> maze;
  24. std::vector<std::vector<coord>> last;
  25.  
  26. std::ifstream inp("input.txt");
  27. inp >> n >> start.y >> start.x >> finish.x >> finish.y;
  28.  
  29. maze.resize(n);
  30. last.resize(n);
  31. for (int i = 0; i < n; ++i) {
  32. maze[i].resize(n);
  33. last[i].resize(n);
  34. }
  35.  
  36. for (int i = 0; i < n; ++i) {
  37. for (int j = 0; j < n; ++j) {
  38. inp >> maze[i][j];
  39. }
  40. }
  41. inp.close();
  42.  
  43. start.x--;
  44. start.y--;
  45. finish.x--;
  46. finish.y--;
  47. std::stack<coord> path;
  48. std::queue<coord> qu;
  49.  
  50. maze[start.x][start.y] = '+';
  51. coordinate.x = start.x;
  52. coordinate.y = start.y;
  53. qu.push(coordinate);
  54.  
  55. while (!qu.empty()) {
  56. coordinate = qu.front();
  57. x = coordinate.x;
  58. y = coordinate.y;
  59. qu.pop();
  60.  
  61. if (coordinate.x == finish.y && coordinate.y == finish.x) {
  62. break;
  63. }
  64.  
  65. if (x > 0 && maze[x - 1][y] == '.') {
  66. check(last, qu, maze, x-1, y, coordinate);
  67. }
  68.  
  69. if (x < n - 1 && maze[x + 1][y] == '.') {
  70. check(last, qu, maze, x+1, y, coordinate);
  71. }
  72.  
  73. if (y > 0 && maze[x][y - 1] == '.') {
  74. check(last, qu, maze, x, y-1, coordinate);
  75. }
  76.  
  77. if (y < n - 1 && maze[x][y + 1] == '.') {
  78. check(last, qu, maze, x, y+1, coordinate);
  79. }
  80. }
  81.  
  82. while (coordinate.x != start.x || coordinate.y != start.y) {
  83. path.push(coordinate);
  84. coordinate = last[coordinate.x][coordinate.y];
  85. }
  86. int res = 0;
  87. res = path.size();
  88.  
  89. std::ofstream outp("output.txt");
  90.  
  91. outp << res;
  92. outp.close();
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement