fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. const int dx[4] = {-1, 1, 0, 0};
  6. const int dy[4] = {0, 0, -1, 1};
  7.  
  8. int main() {
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     int n, m;
  13.     cin >> n >> m;
  14.  
  15.     vector<vector<int> > a(n + 1, vector<int>(m + 1));
  16.     vector<vector<int> > day(n + 1, vector<int>(m + 1, -1));
  17.  
  18.     queue<pair<int, int> > q;
  19.  
  20.     for (int i = 1; i <= n; i++) {
  21.         for (int j = 1; j <= m; j++) {
  22.             cin >> a[i][j];
  23.  
  24.             if (a[i][j] == 0) {
  25.                 day[i][j] = 0;
  26.                 q.push(make_pair(i, j));
  27.             }
  28.         }
  29.     }
  30.  
  31.     int u1, v1, u2, v2;
  32.     cin >> u1 >> v1 >> u2 >> v2;
  33.  
  34.     // BFS đa nguồn tính ngày tan
  35.     while (!q.empty()) {
  36.         pair<int, int> cur = q.front();
  37.         q.pop();
  38.  
  39.         int x = cur.first;
  40.         int y = cur.second;
  41.  
  42.         for (int k = 0; k < 4; k++) {
  43.             int nx = x + dx[k];
  44.             int ny = y + dy[k];
  45.  
  46.             if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
  47.             if (day[nx][ny] != -1) continue;
  48.  
  49.             day[nx][ny] = day[x][y] + 1;
  50.             q.push(make_pair(nx, ny));
  51.         }
  52.     }
  53.  
  54.     // Dijkstra minimax
  55.     vector<vector<int> > dist(n + 1, vector<int>(m + 1, INF));
  56.  
  57.     priority_queue<
  58.         pair<int, pair<int, int> >,
  59.         vector<pair<int, pair<int, int> > >,
  60.         greater<pair<int, pair<int, int> > >
  61.     > pq;
  62.  
  63.     dist[u1][v1] = day[u1][v1];
  64.     pq.push(make_pair(dist[u1][v1], make_pair(u1, v1)));
  65.  
  66.     while (!pq.empty()) {
  67.         pair<int, pair<int, int> > cur = pq.top();
  68.         pq.pop();
  69.  
  70.         int d = cur.first;
  71.         int x = cur.second.first;
  72.         int y = cur.second.second;
  73.  
  74.         if (d != dist[x][y]) continue;
  75.  
  76.         if (x == u2 && y == v2) {
  77.             cout << d << '\n';
  78.             return 0;
  79.         }
  80.  
  81.         for (int k = 0; k < 4; k++) {
  82.             int nx = x + dx[k];
  83.             int ny = y + dy[k];
  84.  
  85.             if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
  86.  
  87.             int nd = max(dist[x][y], day[nx][ny]);
  88.  
  89.             if (nd < dist[nx][ny]) {
  90.                 dist[nx][ny] = nd;
  91.                 pq.push(make_pair(nd, make_pair(nx, ny)));
  92.             }
  93.         }
  94.     }
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5 7
0 1 1 1 1 1 0
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
0 1 1 1 1 1 0
1 1 3 4
stdout
copy 
2
https://ideone.com/cXOdg5
language:
C++14 (gcc 8.3)
created:
1 day 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!