fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef vector<int> vi;
  7. typedef vector<ld> vld;
  8. typedef vector<ll> vll;
  9. typedef vector<pair<ll, ll>> vp;
  10. typedef pair<int, int> pii;
  11. typedef pair<ll, ll> pll;
  12. #define fr first
  13. #define sc second
  14. #define all(a) a.begin(),a.end()
  15.  
  16.  
  17. void Hendi() {
  18.     ios_base::sync_with_stdio(0);
  19.     cin.tie(0);
  20.     cout.tie(0);
  21. #ifndef ONLINE_JUDGE
  22.     freopen("input.txt", "r", stdin);
  23.     freopen("output.txt", "w", stdout);
  24.     freopen("error.txt", "w", stderr);
  25. #endif
  26. }
  27.  
  28. const ll INF = 1e18;
  29. const ll MOD = 1e9 + 7;
  30. const double EPS = 1e-7;
  31. const int N = 1e6 + 5;
  32. const int N1 = 1e5 + 5;
  33. int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  35. char di[] = {'R', 'L', 'D', 'U'};
  36.  
  37. ll mul(ll a, ll b) {
  38.     return ((a % MOD) * (b % MOD)) % MOD;
  39. }
  40.  
  41. ll sub(ll a, ll b) {
  42.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  43. }
  44.  
  45. ll add(ll a, ll b) {
  46.     return ((a % MOD) + (b % MOD)) % MOD;
  47. }
  48.  
  49. int n, m, O, st_row, st_col, end_row, end_col;
  50. vector<pii> obs_r, obs_c;
  51. map<pii, ll> dist;
  52. ll ans;
  53.  
  54. void bfs() {
  55.     queue<pii> q;
  56.     q.push({st_row, st_col});
  57.     dist[{st_row, st_col}] = 0;
  58.     while (!q.empty()) {
  59.         int x = q.front().fr, y = q.front().sc;
  60.         q.pop();
  61.         auto row = lower_bound(all(obs_r), make_pair(x, y));
  62.         auto col = lower_bound(all(obs_c), make_pair(y, x));
  63.         // Row
  64.         int R = row->fr, C = row->sc;
  65.         // right
  66.         if (end_row == x && end_col > y && end_col < C)ans = min(ans, dist[{x, y}] + 1);
  67.         if (dist[{x, y}] + 1 < dist[{R, C - 1}]) {
  68.             dist[{R, C - 1}] = dist[{x, y}] + 1;
  69.             q.push({R, C - 1});
  70.         }
  71.         row--;
  72.         R = row->fr, C = row->sc;
  73.         // left
  74.         if (end_row == x && end_col < y && end_col > C) ans = min(ans, dist[{x, y}] + 1);
  75.         if (dist[{x, y}] + 1 < dist[{R, C + 1}]) {
  76.             dist[{R, C + 1}] = dist[{x, y}] + 1;
  77.             q.push({R, C + 1});
  78.         }
  79.         // Col
  80.         R = col->sc, C = col->fr;
  81.         // down
  82.         if (end_col == y && end_row > x && end_row < R)ans = min(ans, dist[{x, y}] + 1);
  83.         if (dist[{x, y}] + 1 < dist[{R - 1, C}]) {
  84.             dist[{R - 1, C}] = dist[{x, y}] + 1;
  85.             q.push({R - 1, C});
  86.         }
  87.         col--;
  88.         R = col->sc, C = col->fr;
  89.         // up
  90.         if (end_col == y && end_row < x && end_row > R) ans = min(ans, dist[{x, y}] + 1);
  91.         if (dist[{x, y}] + 1 < dist[{R + 1, C}]) {
  92.             dist[{R + 1, C}] = dist[{x, y}] + 1;
  93.             q.push({R + 1, C});
  94.         }
  95.     }
  96. }
  97.  
  98. void solve() {
  99.     cin >> n >> m >> O;
  100.     cin >> st_row >> st_col >> end_row >> end_col;
  101.     int x, y;
  102.     for (int i = 0; i < O; ++i) {
  103.         cin >> x >> y;
  104.         obs_r.push_back({x, y});
  105.         obs_c.push_back({y, x});
  106.         dist[{x - 1, y}] = INF;
  107.         dist[{x + 1, y}] = INF;
  108.         dist[{x, y - 1}] = INF;
  109.         dist[{x, y + 1}] = INF;
  110.     }
  111.     if (st_row == end_row && st_col == end_col) return void(cout << "0\n");
  112.     for (int i = 0; i < n; ++i) {
  113.         dist[{i, m - 1}] = INF;
  114.         dist[{i, 0}] = INF;
  115.         obs_r.push_back({i, m});
  116.         obs_r.push_back({i, -1});
  117.     }
  118.     for (int i = 0; i < m; ++i) {
  119.         dist[{0, i}] = INF;
  120.         dist[{n - 1, i}] = INF;
  121.         obs_c.push_back({i, n});
  122.         obs_c.push_back({i, -1});
  123.     }
  124.     sort(all(obs_r));
  125.     sort(all(obs_c));
  126.     ans = INF;
  127.     bfs();
  128.     cout << (ans == INF ? -1 : ans) << '\n';
  129.     dist.clear();
  130.     obs_r.clear();
  131.     obs_c.clear();
  132. }
  133.  
  134. int main() {
  135.     freopen("maze.in", "r", stdin);
  136.     Hendi();
  137.     int T = 1;
  138.     cin >> T;
  139.     while (T--) {
  140.         solve();
  141.     }
  142. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/f1MM72
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!