fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long 
  3. #define pii pair<int,int>
  4. #define fi first 
  5. #define se second 
  6.  
  7. using namespace std;
  8.  
  9. const int N = 17;
  10. const int M = 1e4 + 7;
  11. const int inf = 1e15;
  12.  
  13. int dx[5] = {-1, 0, 1, 0};
  14. int dy[5] = {0, 1, 0, -1};
  15. int n, m, k, q;
  16. char a[N][M];
  17. int dp[N][M];
  18. struct Data{
  19.     vector <int> a, b, w;
  20. } e[N][M];
  21.  
  22. bool check(int x, int y){
  23.     return (x >= 1 && y >= 1 && x <= n && y <= m && a[x][y] != '#');
  24. }
  25.  
  26. void bfs(int u, int v){
  27.     priority_queue <pair<int,pii>, vector <pair<int,pii>>, greater <pair<int,pii>>> q;
  28.     q.push({0, {u, v}});
  29.     for (int i = 1; i <= n; i ++){
  30.         for (int j = 1; j <= m; j ++){
  31.             dp[i][j] = inf;
  32.         }
  33.     }
  34.     dp[u][v] = 0;
  35.     while (!q.empty()){
  36.         u = q.top().se.fi;
  37.         v = q.top().se.se;
  38.         int w = q.top().fi;
  39.         q.pop();
  40.         if (w > dp[u][v]) continue;
  41.         for (int i = 0; i < 4; i ++){
  42.             int x = u + dx[i];
  43.             int y = v + dy[i];
  44.             if (dp[x][y] > dp[u][v] + 1 && check(x, y)){
  45.                 dp[x][y] = dp[u][v] + 1;
  46.                 q.push({dp[x][y], {x, y}});
  47.             }
  48.         }
  49.         for (int i = 0; i < e[u][v].a.size(); i ++){
  50.             int x = e[u][v].a[i];
  51.             int y = e[u][v].b[i];
  52.             int w = e[u][v].w[i];
  53.             if (dp[x][y] > dp[u][v] + w){
  54.                 dp[x][y] = dp[u][v] + w;
  55.                 q.push({dp[x][y], {x, y}});
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. void sub1(){
  62.     while (q --){
  63.         int u, v, x, y;
  64.         cin >> u >> v >> x >> y;
  65.         bfs(u, v);
  66.         cout << (dp[x][y] == inf ? - 1 : dp[x][y]) << '\n';
  67.     }
  68.     return;
  69. }
  70.  
  71. void sub2(){
  72.     int dp[M];
  73.     for (int i = 0; i <= m; i ++) dp[i] = 0;
  74.     for (int i = 1; i <= m; i ++) dp[i] = dp[i - 1] + (a[1][i] == '#');
  75.     while (q --){
  76.         int u, v, x, y;
  77.         cin >> u >> v >> x >> y;
  78.         if (v <= y && dp[y] - dp[v - 1] == 0) cout << y - v << '\n';
  79.         else if (v > y && dp[v] - dp[y - 1] == 0) cout << v - y << '\n';
  80.         else cout << - 1 << '\n';
  81.     }
  82. }
  83.  
  84. signed main(){
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(0); cout.tie(0);
  87.     freopen("maze.inp", "r", stdin);
  88.     freopen("maze.out", "w", stdout);
  89.     cin >> n >> m >> k >> q;
  90.     for (int i = 1; i <= n; i ++){
  91.         for (int j = 1; j <= m; j ++){
  92.             cin >> a[i][j];
  93.         }
  94.     }
  95.     for (int i = 1; i <= k; i ++){
  96.         int x, y, u, v, w;
  97.         cin >> x >> y >> u >> v >> w;
  98.         e[x][y].a.push_back(u);
  99.         e[x][y].b.push_back(v);
  100.         e[x][y].w.push_back(w);
  101.         e[u][v].a.push_back(x);
  102.         e[u][v].b.push_back(y);
  103.         e[u][v].w.push_back(w);
  104.     }
  105.     if (m <= 100 && q <= 100){
  106.         sub1();
  107.     }
  108.     if (k == 0 && n == 1){
  109.         sub2();
  110.     }
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 17140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/raiQoa
language:
C++ (gcc 8.3)
created:
15 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!