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