Facebook
From me, 1 Month ago, written in C++.
Embed
Download Paste or View Raw
Hits: 160
  1. #include <stdio.h>
  2.  
  3. #include <iostream>
  4. #include <queue>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. int n, m, p, q, s, t, r, c;
  10. vector<vector<int>> visited;
  11. vector<vector<int>> dist;
  12. vector<pair<int, int>> directs = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
  13.  
  14. int bfs(pair<int, int> s, pair<int, int> e) {
  15.     dist.assign(n, vector<int>(n, -1));
  16.     queue<pair<int, int>> q;
  17.     q.push(s);
  18.     dist[s.first][s.second] = 0;
  19.     visited[s.first][s.second] = 1;
  20.  
  21.     pair<int, int> u, v;
  22.     while (!q.empty()) {
  23.         u = q.front();
  24.         q.pop();
  25.         for (int id = 0; id < directs.size(); id++) {
  26.             int x = u.first, y = u.second;
  27.             while (true) {
  28.                 x += directs[id].first;
  29.                 y += directs[id].second;
  30.  
  31.                 if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] == -1)
  32.                     break;
  33.                 if (visited[x][y] != 0) continue;
  34.  
  35.                 v = {x, y};
  36.                 if (!visited[v.first][v.second]) {
  37.                     visited[v.first][v.second] = 1;
  38.                     dist[v.first][v.second] = dist[u.first][u.second] + 1;
  39.                    if (v == e) return dist[e.first][e.second];
  40.                     q.push(v);
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     return dist[e.first][e.second];
  46. }
  47. int main() {
  48.     cin >> n >> m >> p >> q >> s >> t;
  49.     p--;
  50.     q--;
  51.     s--;
  52.     t--;
  53.  
  54.     visited.assign(n, vector<int>(n, 0));
  55.  
  56.     for (int i = 0; i < m; i++) {
  57.         cin >> r >> c;
  58.         r--;
  59.         c--;
  60.         visited[r][c] = -1;
  61.     }
  62.  
  63.     cout << bfs({p, q}, {s, t});
  64.  
  65.     return 0;
  66. }
  67.