fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 1001;
  5. typedef pair<int, int> ii;
  6. const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  7. const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  8. int n, s, t, u, v;
  9. int a[maxn][maxn];
  10. int path[maxn][maxn];
  11.  
  12. void inp() {
  13. cin >> n >> s >> t >> u >> v;
  14. for (int i = 1; i <= n; i++) {
  15. for (int j = 1; j <= n; j++) {
  16. cin >> a[i][j];
  17. path[i][j] = INT_MAX; // Initialize path with large value
  18. }
  19. }
  20. }
  21.  
  22. void BFS(int i, int j) {
  23. queue<ii> q;
  24. q.push({i, j});
  25. path[i][j] = 0; // Starting point
  26. while (!q.empty()) {
  27. ii p = q.front();
  28. q.pop();
  29. for (int k = 0; k < 8; k++) {
  30. int i1 = p.first + dx[k];
  31. int j1 = p.second + dy[k];
  32. if (i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= n && a[i1][j1]) {
  33. q.push({i1, j1});
  34. path[i1][j1] = min(path[i1][j1], path[p.first][p.second] + 1);
  35. a[i1][j1] = 0; // Mark visited cell
  36. }
  37. }
  38. }
  39. }
  40.  
  41. int main() {
  42. inp();
  43. BFS(s, t);
  44. if (path[u][v] == INT_MAX) {
  45. cout << "-1\n";
  46. } else {
  47. cout << path[u][v] << endl;
  48. }
  49. return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5640KB
stdin
10
9 6 9 3
1 1 0 1 1 1 1 0 0 1
0 0 1 0 0 1 0 1 0 1
1 1 1 1 0 0 0 1 1 0
1 0 0 0 1 0 0 0 1 1
1 0 1 0 0 1 0 1 1 0
0 0 1 1 0 1 0 0 0 0
1 1 0 1 0 1 1 0 0 0
0 0 0 1 1 0 1 1 0 1
1 0 1 0 0 1 0 0 1 1
0 1 1 1 1 0 1 0 1 1
stdout
3