Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. int n;
  7.  
  8. vector<vector<char>> grid;
  9. vector<vector<int>> shortestPaths;
  10.  
  11. vector<int>xd{ -1,0, 0, 1 };
  12. vector<int>yd{ 0,1,-1, 0 };
  13.  
  14. bool isValid(int x, int y)
  15. {
  16. return x >= 0 && y >= 0
  17. && x < n && y < n
  18. && grid[x][y] == '.'
  19. && shortestPaths[x][y] == -1;
  20. }
  21.  
  22. void bfs(int sx, int sy, int ex, int ey)
  23. {
  24. if (isValid(sx, sy))
  25. {
  26. shortestPaths[sx][sy] = 0;
  27. }
  28. else return;
  29.  
  30. queue<pair<int, int>> Q;
  31. Q.push({ sx,sy });
  32.  
  33. while (!Q.empty())
  34. {
  35. pair<int, int>p = Q.front();
  36. Q.pop();
  37.  
  38. for (size_t i = 0; i < 4; ++i)
  39. {
  40. int newX = p.first + xd[i];
  41. int newY = p.second + yd[i];
  42.  
  43. while (isValid(newX, newY))
  44. {
  45. Q.push({ newX,newY });
  46. shortestPaths[newX][newY] = shortestPaths[p.first][p.second] + 1;
  47. newX += xd[i];
  48. newY += yd[i];
  49. }
  50. }
  51.  
  52. }
  53. }
  54.  
  55. int main()
  56. {
  57. int startX, endY, goalX, goalY, i, j;
  58. cin >> n;
  59.  
  60. grid.assign(n, vector<char>(n));
  61. shortestPaths.assign(n, vector<int>(n, -1));
  62.  
  63. for (i = 0; i < n; ++i)
  64. {
  65. for (j = 0; j < n; ++j)
  66. {
  67. cin >> grid[i][j];
  68. }
  69. }
  70. cin >> startX >> endY >> goalX >> goalY;
  71.  
  72. bfs(startX, endY, goalX, goalY);
  73.  
  74. cout << shortestPaths[goalX][goalY];
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement