Advertisement
stas224

Untitled

Dec 9th, 2021
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8. int n = 0, m = 0, x0 = 0, y0 = 0, x1 = 0, y1 = 0;
  9. cin >> n >> m;
  10. vector<vector<int> > v(n, vector<int>(m, n * m));
  11. for (int i = 0; i < n; i++)
  12. {
  13. for (int j = 0; j < m; j++)
  14. {
  15. int x;
  16. cin >> x;
  17. if (x != 0)
  18. v[i][j] = -1;
  19.  
  20. }
  21. }
  22. cin >> x0 >> y0 >> x1 >> y1;
  23. x0--; y0--; x1--; y1--;
  24. v[y0][x0] = 0;
  25. queue<pair<int, int> > q;
  26. q.push({ y0, x0 });
  27. while (!q.empty()) {
  28. int y = q.front().first;
  29. int x = q.front().second;
  30. q.pop();
  31. if (x - 1 >= 0 && v[y][x] + 1 < v[y][x -1] && v[y][x -1] != -1) {
  32. v[y][x-1] = v[y][x] + 1;
  33. q.push({ y,x - 1 });
  34. }
  35. if (x + 1 < m && v[y][x] + 1 < v[y][x + 1] && v[y ][x + 1] != -1) {
  36. v[y][x + 1] = v[y][x] + 1;
  37. q.push({y, x + 1});
  38. }
  39. if (y - 1 >= 0 && v[y][x] + 1 < v[y - 1][x] && v[y - 1][x] != -1) {
  40. v[y -1][x] = v[y][x] + 1;
  41. q.push({ y - 1 ,x});
  42. }
  43. if (y + 1 < n && v[y][x] + 1 < v[y + 1][x] && v[y + 1][x] != -1) {
  44. v[y + 1][x] = v[y][x] + 1;
  45. q.push({ y + 1,x });
  46. }
  47. }
  48. if (v[y1][x1] == m * n || v[y1][x1] == -1)
  49. cout << -1;
  50. else
  51. cout << v[y1][x1];
  52. return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement