Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. int A[100][100], startX, startY, endX, endY;
  7. int used[100][100];
  8.  
  9. struct pos
  10. {
  11. int x;
  12. int y;
  13. int dist;
  14. };
  15.  
  16. bool valid(int i, int j, int n)
  17. {
  18. if (i < 0 || i >= n || j < 0 || j >= n)
  19. return 0;
  20. if (A[i][j] == 1)
  21. return 0;
  22. return 1;
  23. }
  24.  
  25. int bfs(int n)
  26. {
  27. queue<pos> q;
  28. pos startPos;
  29. startPos.x = startX;
  30. startPos.y = startY;
  31. startPos.dist = 0;
  32. q.push(startPos);
  33. while (!q.empty())
  34. {
  35. pos currPos = q.front();
  36. if (currPos.x == endX && currPos.y == endY)
  37. return currPos.dist;
  38. if (!used[currPos.x][currPos.y])
  39. {
  40. if (valid(currPos.x + 1, currPos.y, n))
  41. {
  42. pos newPos;
  43. newPos.x = currPos.x + 1;
  44. newPos.y = currPos.y;
  45. newPos.dist = currPos.dist + 1;
  46. q.push(newPos);
  47. }
  48. if (valid(currPos.x - 1, currPos.y, n))
  49. {
  50. pos newPos;
  51. newPos.x = currPos.x - 1;
  52. newPos.y = currPos.y;
  53. newPos.dist = currPos.dist + 1;
  54. q.push(newPos);
  55. }
  56. if (valid(currPos.x, currPos.y + 1, n))
  57. {
  58. pos newPos;
  59. newPos.x = currPos.x;
  60. newPos.y = currPos.y + 1;
  61. newPos.dist = currPos.dist + 1;
  62. q.push(newPos);
  63. }
  64. if (valid(currPos.x, currPos.y - 1, n))
  65. {
  66. pos newPos;
  67. newPos.x = currPos.x;
  68. newPos.y = currPos.y - 1;
  69. newPos.dist = currPos.dist + 1;
  70. used[currPos.x][currPos.y - 1] = 1;
  71. q.push(newPos);
  72. }
  73. used[currPos.x][currPos.y] = 1;
  74. }
  75. q.pop();
  76. }
  77. }
  78.  
  79. int main()
  80. {
  81. int n;
  82. cin >> n;
  83.  
  84. for (int i = 0; i < n; ++i)
  85. for (int j = 0; j < n; ++j)
  86. cin >> A[i][j];
  87.  
  88. cin >> startX >> startY >> endX >> endY;
  89. cout << bfs(n) << endl;
  90.  
  91. return 0;
  92. }
  93.  
  94. /*
  95. 3
  96. 0 0 0
  97. 0 0 0
  98. 0 0 0
  99. 0 0 2 2
  100. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement