Advertisement
Guest User

Untitled

a guest
Nov 21st, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include "Cell.hpp"
  4.  
  5. template<typename T>
  6. T** makeMatrix(const size_t N)
  7. {
  8. T** matrix = new T*[N];
  9. for (int i = 0; i < N; ++i)
  10. matrix[i] = new T[N];
  11. return matrix;
  12. }
  13.  
  14. template<typename T>
  15. void printMatrix(T** matrix, const size_t N)
  16. {
  17. for (int i = 0; i < N; ++i)
  18. {
  19. for (int j = 0; j < N; ++j)
  20. {
  21. std::cout << matrix[i][j] << ' ';
  22. }
  23. std::cout << std::endl;
  24. }
  25. }
  26.  
  27. void markAsVisited(bool** visitedMatrix, const int i, const int j)
  28. {
  29. visitedMatrix[i][j] = 1;
  30. }
  31.  
  32. void setCellsValues(char** inputMatrix, bool** visitedMatrix, const size_t N)
  33. {
  34. for (int i = 0; i < N; ++i)
  35. {
  36. for (int j = 0; j < N; ++j)
  37. {
  38. std::cin >> inputMatrix[i][j];
  39. if (inputMatrix[i][j] == 'X')
  40. markAsVisited(visitedMatrix, i, j);
  41. }
  42. }
  43. }
  44.  
  45. bool possibleUP(const int x, const int y,bool** visitedMatrix)
  46. {
  47. return x - 1 >= 0 && visitedMatrix[x - 1][y] != 1;
  48. }
  49.  
  50. bool possibleDown(const int x,const int y,bool** visitedMatrix,const size_t N)
  51. {
  52. return x + 1 < N && visitedMatrix[x + 1][y] != 1;
  53. }
  54.  
  55. bool possibleLeft(const int x, const int y, bool** visitedMatrix)
  56. {
  57. return y - 1 >= 0 && visitedMatrix[x][y - 1] != 1;
  58. }
  59.  
  60. bool possibleRight(const int x, const int y, bool** visitedMatrix, const size_t N)
  61. {
  62. return y + 1 < N && visitedMatrix[x][y + 1] != 1;
  63. }
  64.  
  65. void move(std::queue<Cell>& cellsQueue, bool** visitedMatrix, const int x, const int y, const int dist)
  66. {
  67. cellsQueue.push(Cell(x, y, dist));
  68. markAsVisited(visitedMatrix, x, y);
  69. }
  70.  
  71. int main()
  72. {
  73. size_t N;
  74. std::cin >> N;
  75.  
  76. char** inputMatrix = makeMatrix<char>(N);
  77. bool** visitedMatrix = makeMatrix<bool>(N);
  78. setCellsValues(inputMatrix, visitedMatrix, N);
  79.  
  80. int xStart, yStart, xEnd, yEnd;
  81. std::cin >> xStart >> yStart >> xEnd >> yEnd;
  82.  
  83. Cell start(xStart, yStart);
  84.  
  85. std::queue<Cell> cellsQueue;
  86. cellsQueue.push(start);
  87. markAsVisited(visitedMatrix, start.x, start.y);
  88.  
  89. while (!cellsQueue.empty())
  90. {
  91. Cell c = cellsQueue.front();
  92. cellsQueue.pop();
  93.  
  94. if (c.x == xEnd && c.y == yEnd)
  95. return c.dist;
  96.  
  97. //go up
  98. if (possibleUP(c.x, c.y, visitedMatrix))
  99. move(cellsQueue, visitedMatrix, c.x - 1, c.y, c.dist + 1);
  100.  
  101. //go down
  102. if (possibleDown(c.x, c.y, visitedMatrix, N))
  103. move(cellsQueue, visitedMatrix, c.x + 1, c.y, c.dist + 1);
  104.  
  105. //go left
  106. if (possibleLeft(c.x, c.y, visitedMatrix))
  107. move(cellsQueue, visitedMatrix, c.x, c.y -1 , c.dist + 1);
  108.  
  109. //go right
  110. if (possibleRight(c.x,c.y,visitedMatrix,N))
  111. move(cellsQueue, visitedMatrix, c.x, c.y + 1, c.dist + 1);
  112. }
  113.  
  114. return -1;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement