fork download
copy 
  1. /**
  2.  *    author:  mamion
  3.  *    created: Tuesday 2024-10-29
  4. **/
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #ifdef LOCAL
  10. #include<cpp-dump-main/cpp-dump.hpp>
  11. #define debug(...) cpp_dump(__VA_ARGS__)
  12. CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
  13. CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
  14. CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
  15. #else
  16. #define debug(...)
  17. #endif // LOCAL
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22.  
  23. struct dsu {
  24.     vector<int> lab;
  25.     dsu(int n) {
  26.         lab.resize(n + 2, -1);
  27.     }
  28.     int find(int u) {
  29.         return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  30.     }
  31.     int join(int u, int v) {
  32.         u = find(u); v = find(v);
  33.         if (u == v) return false;
  34.         lab[u] += lab[v];
  35.         lab[v] = u;
  36.         return true;
  37.     }
  38. };
  39.  
  40. const int N = 2210;
  41. int n, m, k;
  42. char c[N][N];
  43. int sx, sy, fx, fy;
  44.  
  45. int d[N][N];
  46.  
  47. vector<dsu> trai, tren, phai, duoi;
  48.  
  49. void remove4dir(int x, int y) {
  50.     if (x <= n) tren[y].join(x + 1, x);
  51.     if (x >= 1) duoi[y].join(x - 1, x);
  52.     if (y <= m) phai[x].join(y + 1, y);
  53.     if (y >= 1) trai[x].join(y - 1, y);
  54. }
  55.  
  56. void solve() {
  57.     cin >> n >> m >> k;
  58.     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
  59.         cin >> c[i][j];
  60.     cin >> sx >> sy >> fx >> fy;
  61.     trai = phai = vector<dsu>(n + 2, dsu(m));
  62.     tren = duoi = vector<dsu>(m + 2, dsu(n));
  63.     queue<pair<int, int>> q; q.push({sx, sy}); remove4dir(sx, sy);
  64.     while (q.size()) {
  65.         int u = q.front().first, v = q.front().second; q.pop();
  66.         if (u == fx && v == fy) {
  67.             cout << d[u][v];
  68.             return;
  69.         }
  70.         // di len
  71.         while (true) {
  72.             int x = tren[v].find(u), y = v;
  73.             if (x > n || x - u > k || c[x][y] == '#') break;
  74.             remove4dir(x, y);
  75.             q.push({x, y});
  76.             d[x][y] = d[u][v] + 1;
  77.             if (x == fx && y == fy) {
  78.                 cout << d[x][y];
  79.                 return;
  80.             }
  81.         }
  82.         // di xuong
  83.         while (true) {
  84.             int x = duoi[v].find(u), y = v;
  85.             if (x < 1 || u - x > k || c[x][y] == '#') break;
  86.             remove4dir(x, y);
  87.             q.push({x, y});
  88.             d[x][y] = d[u][v] + 1;
  89.             if (x == fx && y == fy) {
  90.                 cout << d[x][y];
  91.                 return;
  92.             }
  93.         }
  94.         // di phai
  95.         while (true) {
  96.             int x = u, y = phai[u].find(v);
  97.             if (y > m || y - v > k || c[x][y] == '#') break;
  98.             remove4dir(x, y);
  99.             q.push({x, y});
  100.             d[x][y] = d[u][v] + 1;
  101.             if (x == fx && y == fy) {
  102.                 cout << d[x][y];
  103.                 return;
  104.             }
  105.         }
  106.         // di trai
  107.         while (true) {
  108.             int x = u, y = trai[u].find(v);
  109.             if (y < 1 || v - y > k || c[x][y] == '#') break;
  110.             remove4dir(x, y);
  111.             q.push({x, y});
  112.             d[x][y] = d[u][v] + 1;
  113.             if (x == fx && y == fy) {
  114.                 cout << d[x][y];
  115.                 return;
  116.             }
  117.         }
  118.     }
  119.     cout << -1;
  120. }
  121.  
  122. int main() {
  123.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  124.  
  125. #ifdef LOCAL
  126.     freopen("main.inp", "r", stdin);
  127.     freopen("main.out", "w", stdout);
  128. #else
  129.     #define file "flash"
  130.     if (fopen(file".inp", "r")) {
  131.         freopen(file".inp", "r", stdin);
  132.         freopen(file".out", "w", stdout);
  133.     }
  134. #endif // LOCAL
  135.  
  136.     int T; T = 1; if (0) cin >> T;
  137.     for (int i = 1; i <= T; i++)
  138.     {
  139.         solve();
  140.     }
  141. }
  142.  
Success #stdin #stdout 0.01s 5668KB
comments (?)
stdin
copy 
3 4 4
....
###.
....
1 1 3 1
stdout
copy 
3
https://ideone.com/Mo4Fcz
language:
C++14 (gcc 8.3)
created:
2 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!