fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 1e3;
  12. const int dx[] = {0, -1, 0, 1};
  13. const int dy[] = {-1, 0, 1, 0};
  14.  
  15. int n, m, dist[maxn + 10][maxn + 10], xs, ys, xt, yt;
  16. ii dir[maxn + 10][maxn + 10][4];
  17. bool vis[maxn + 10][maxn + 10];
  18. char a[maxn + 10][maxn + 10];
  19. deque<ii> dq;
  20.  
  21. bool in_matrix(int x, int y)
  22. {
  23.     return x >= 1 && x <= n && y >= 1 && y <= m;
  24. }
  25. void bfs01(int xs, int ys)
  26. {
  27.     memset(dist, -1, sizeof dist);
  28.     dq.push_back({xs, ys});
  29.     dist[xs][ys] = 0;
  30.  
  31.     while (dq.size())
  32.     {
  33.         ii t = dq.front();
  34.         dq.pop_front();
  35.         int x = t.fi;
  36.         int y = t.se;
  37.  
  38.         if (vis[x][y])
  39.             continue;
  40. //        cout << x << ' ' << y << ' ' << dist[x][y], el;
  41.         vis[x][y] = 1;
  42.         for (int k = 0; k < 4; k++)
  43.         {
  44.             int nx = x + dx[k];
  45.             int ny = y + dy[k];
  46.  
  47.             if (!in_matrix(nx, ny))
  48.                 continue;
  49.             if (a[nx][ny] != '.' && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y]))
  50.             {
  51.                 dist[nx][ny] = dist[x][y];
  52.                 dq.push_front({nx, ny});
  53.             }
  54.             ii nt = dir[x + dx[k]][y + dy[k]][k];
  55.             nx = nt.fi;
  56.             ny = nt.se;
  57.             if (!in_matrix(nx, ny))
  58.                 continue;
  59. //            cout << x << ' ' << y << ' ' << nx << ' ' << ny, el;
  60.             if (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y] + 1)
  61.             {
  62.                 dist[nx][ny] = dist[x][y] + 1;
  63.                 dq.push_back({nx, ny});
  64.             }
  65.         }
  66.     }
  67. }
  68.  
  69. int main()
  70. {
  71.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  72.     if (fopen("SHORTEST.INP", "r"))
  73.     {
  74.         freopen("SHORTEST.INP", "r", stdin);
  75.         freopen("SHORTEST.OUT", "w", stdout);
  76.     }
  77.  
  78.     cin >> n >> m;
  79.     for (int i = 0; i <= n; i++)
  80.         for (int j = 0; j <= m; j++)
  81.             for (int k = 0; k < 4; k++)
  82.                 dir[i][j][k] = {-1, -1};
  83.     for (int i = 1; i <= n; i++)
  84.         for (int j = 1; j <= m; j++)
  85.         {
  86.             cin >> a[i][j];
  87.             if (a[i][j] == 'S')
  88.                 xs = i, ys = j;
  89.             else if (a[i][j] == 'T')
  90.                 xt = i, yt = j;
  91.             if (a[i][j] == '#')
  92.                 for (int k = 0; k < 4; k++)
  93.                     dir[i][j][k] = {i, j};
  94.         }
  95.     for (int i = 1; i <= n; i++)
  96.         for (int j = 1; j <= m; j++)
  97.         {
  98.             dir[i][j][0] = max(dir[i][j][0], dir[i][j - 1][0]);
  99.             dir[i][j][1] = max(dir[i][j][1], dir[i - 1][j][1]);
  100.         }
  101.     for (int i = n; i >= 1; i--)
  102.         for (int j = m; j >= 1; j--)
  103.         {
  104.             if (dir[i][j][2].fi == -1)
  105.                 dir[i][j][2] = dir[i][j + 1][2];
  106.             if (dir[i][j][3].fi == -1)
  107.                 dir[i][j][3] = dir[i + 1][j][3];
  108.         }
  109. //    for (int k = 0; k < 4; k++)
  110. //    {
  111. //        for (int i = 1; i <= n; i++)
  112. //        {
  113. //            for (int j = 1; j <= m; j++)
  114. //                cout << "( " << dir[i][j][k].fi << ' ' << dir[i][j][k].se << " ) ";
  115. //            el;
  116. //        }
  117. //        el;
  118. //    }
  119.     bfs01(xs, ys);
  120.     cout << dist[xt][yt];
  121. }
  122.  
Success #stdin #stdout 0.01s 9640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9pCZxk
language:
C++14 (gcc 8.3)
created:
10 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!