fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. struct node
  9. {
  10.     int x, y, dir, dis;
  11. };
  12.  
  13. const int maxn = 1e3;
  14. const int dx[] = {-1, 0, 1, 0};
  15. const int dy[] = {0, 1, 0, -1};
  16. const int INF = 1e9;
  17.  
  18. int n, m, d, dist[maxn + 10][maxn + 10][4], xa, ya, xb, yb, ans = INF;
  19. char a[maxn + 10][maxn + 10];
  20. bool vis[maxn + 10][maxn + 10][4];
  21.  
  22. bool check(int x, int y)
  23. {
  24.     return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '.';
  25. }
  26. void bfs01(int s, int t)
  27. {
  28.     deque<node> dq;
  29.     for (int i = 1; i <= n; i++)
  30.         for (int j = 1; j <= m; j++)
  31.             for (int k = 0; k < 4; k++)
  32.             {
  33.                 dist[i][j][k] = INF;
  34.                 vis[i][j][k] = 0;
  35.             }
  36.     for (int k = 0; k < 4; k++)
  37.     {
  38.         dist[s][t][k] = 0;
  39.         dq.push_front({s, t, k, 0});
  40.     }
  41.     while (!dq.empty())
  42.     {
  43.         node t = dq.front();
  44.         dq.pop_front();
  45.         int x = t.x;
  46.         int y = t.y;
  47.         int dir = t.dir;
  48.         int free_dis = t.dis;
  49.  
  50.         if (vis[x][y][dir]) continue;
  51.         vis[x][y][dir] = 1;
  52.  
  53.         for (int k = 0; k < 4; k++)
  54.         {
  55.             int nx = x + dx[k];
  56.             int ny = y + dy[k];
  57.             if (!check(nx, ny)) continue;
  58.             if (free_dis && dir == k && dist[nx][ny][k] > dist[x][y][dir])
  59.             {
  60.                 dist[nx][ny][k] = dist[x][y][dir];
  61.                 dq.push_front({nx, ny, k, free_dis - 1});
  62.             }
  63.             else if (dist[nx][ny][k] > dist[x][y][dir] + 1)
  64.             {
  65.                 dist[nx][ny][k] = dist[x][y][dir] + 1;
  66.                 dq.push_back({nx, ny, k, d - 1});
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. int main()
  73. {
  74.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  75.     if (fopen("ENERGY.INP", "r"))
  76.     {
  77.         freopen("ENERGY.INP", "r", stdin);
  78.         freopen("ENERGY.OUT", "w", stdout);
  79.     }
  80.  
  81.     cin >> n >> m >> d;
  82.     for (int i = 1; i <= n; i++)
  83.         for (int j = 1; j <= m; j++)
  84.             cin >> a[i][j];
  85.     cin >> xa >> ya >> xb >> yb;
  86.     bfs01(xa, ya);
  87.     for (int k = 0; k < 4; k++)
  88.         ans = min(ans, dist[xb][yb][k]);
  89.     if (ans == INF) return cout << -1, 0;
  90.     cout << ans;
  91. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wYBTr6
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!