fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3.  
  4. #define __Shibae__      signed main()
  5. #define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define fiopen(Path)    freopen(Path".INP", "r", stdin); freopen(Path".OUT", "w", stdout);
  7. #define fipen(Path)     freopen(Path".INP", "r", stdin);
  8. #define sz(s)           (int)s.size()
  9. #define all(x)          x.begin(), x.end()
  10. #define maxHeap         priority_queue<int>
  11. #define minHeap         priority_queue<int, vector<int>, greater<int>>
  12. #define getBit(x, k)    (((x) >> (k)) & 1)
  13. #define MASK(i)         (1LL << (i))
  14. #define SQR(x)          (1LL * ((x) * (x)))
  15. #define db              double
  16. #define ld              long double
  17. #define ui              unsigned int
  18. #define ll              long long
  19. #define ii              pair<int, int>
  20. #define pli             pair<ll, int>
  21. #define pil             pair<int, ll>
  22. #define pll             pair<ll, ll>
  23. #define fi              first
  24. #define se              second
  25.  
  26. #define FOR(i, a, b)    for(int i = a, _b = b; i <= _b; i += 1)
  27. #define FOD(i, a, b)    for(int i = a, _b = b; i >= _b; i -= 1)
  28. #define REP(i, a)       for(int i = 0, _a = a; i < _a; i++)
  29. #define pb              push_back
  30. #define fau(u, a)       for(auto &u : a)
  31.  
  32. using namespace std;
  33.  
  34. const ll mod = 1e9 + 7;
  35. const int INF = 1e9 + 7;
  36. const ll INFLL = (ll)2e18 + 7LL;
  37. const ld PI = acos(-1);
  38. const int MAX = 2210;
  39.  
  40. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  41. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  42.  
  43. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  44.  
  45. ll Rand(ll l, ll r) 
  46. {
  47.     return l + rd() % (r - l + 1);
  48. }
  49.  
  50. template<class SHIBA, class ENGINE>
  51.     bool minimize(SHIBA &x, const ENGINE y)
  52.     {
  53.         if(x > y)
  54.         {
  55.             x = y;
  56.             return true;
  57.         } 
  58.         else return false;
  59.     }
  60. template<class SHIBA, class ENGINE>
  61.     bool maximize(SHIBA &x, const ENGINE y)
  62.     {
  63.         if(x < y)
  64.         {
  65.             x = y;
  66.             return true;
  67.         }
  68.         else return false;
  69.     }
  70.  
  71.  
  72. /* Template by: Nguyen Nhat Anh from Luong Van Chanh High School for the gifted */
  73. /* From Min Tuoi with love */
  74.         /**       TRY HARD        **/
  75.         /**          ORZ          **/
  76.  
  77. /* -----------------[ MAIN CODE ]----------------- */
  78.  
  79. int n, m, k;
  80. int a[MAX][MAX];
  81. int f[4][MAX][MAX];
  82. int xs, ys, xt, yt; 
  83.  
  84. int get(int x)
  85. {
  86.     return x / k + (x % k != 0);
  87. }
  88.  
  89. struct owo
  90. {
  91.     int x, y, direct, rlen, len;
  92.  
  93.     bool operator < (const owo &b) const
  94.     {
  95.         return rlen + get(len) > b.rlen + get(b.len);
  96.     }
  97. };
  98.  
  99. void input()
  100. {
  101.     cin >> n >> m >> k;
  102.  
  103.     FOR(i, 1, n) FOR(j, 1, m)
  104.     {
  105.         char c; cin >> c;
  106.         a[i][j] = (c == '.' ? 1 : -1);
  107.         f[0][i][j] = f[1][i][j] = f[2][i][j] = f[3][i][j] = INF;
  108.     }
  109.  
  110.     cin >> xs >> ys >> xt >> yt;
  111. }
  112.  
  113. bool inside(int u, int v)
  114. {
  115.     return u >= 1 && u <= n && v >= 1 && v <= m;
  116. }
  117.  
  118. void dijk()
  119. {
  120.     priority_queue<owo> pq;
  121.  
  122.     f[0][xs][ys] = f[1][xs][ys] = f[2][xs][ys] = f[3][xs][ys] = 0;
  123.  
  124.     pq.push({xs, ys, 0, 0, 0});
  125.     pq.push({xs, ys, 1, 0, 0});
  126.     pq.push({xs, ys, 2, 0, 0});
  127.     pq.push({xs, ys, 3, 0, 0});
  128.  
  129.     while(pq.size())
  130.     {
  131.         int x = pq.top().x;
  132.         int y = pq.top().y;
  133.         int dir = pq.top().direct;
  134.         int rlen = pq.top().rlen;
  135.         int len = pq.top().len;
  136.         // cout << x << " " << y << " " << rlen + get(len) << "\n";
  137.  
  138.         pq.pop();
  139.  
  140.         if (rlen + get(len) > f[dir][x][y]) continue;
  141.         if (x == xt && y == yt) return;
  142.  
  143.         int cur = get(len+1);
  144.         int cc = get(len);
  145.  
  146.         REP(i, 4)
  147.         {
  148.             int u = x + dx[i];
  149.             int v = y + dy[i];
  150.  
  151.             if (inside(u, v) && a[u][v] != -1)
  152.             {
  153.                 if (i == dir)
  154.                 {
  155.                     if (minimize(f[dir][u][v], rlen + cur))
  156.                     {
  157.                         pq.push({u, v, dir, rlen, len + 1});
  158.                     }
  159.                 }
  160.                 else
  161.                 {
  162.                     if (minimize(f[i][u][v], rlen + cc + 1))
  163.                     {
  164.                         pq.push({u, v, i, rlen + cc, 1});
  165.                     }
  166.                 }
  167.             }
  168.         }
  169.     }
  170. }
  171.  
  172. void solve()
  173. {
  174.     if (xs == xt && ys == yt)
  175.     {
  176.         cout << 0;
  177.         return;
  178.     }
  179.  
  180.     dijk();
  181.  
  182.     int res = INF;
  183.  
  184.     REP(i, 4)
  185.     {
  186.         // cout << f[i][xt][yt] << " ";
  187.         minimize(res, f[i][xt][yt]);
  188.     }    
  189.  
  190.     cout << (res == INF ? -1 : res);
  191. }
  192.  
  193. __Shibae__
  194. {
  195.     IOS
  196.     fipen("m");
  197.  
  198.     input();
  199.     solve();
  200.  
  201.     return 0;
  202. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xdkfXy
language:
C++ (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!