fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <queue>
  5. #include <vector>
  6. #include <cstring>
  7. using namespace std;
  8.  
  9. vector<vector<short>> dist;
  10. vector<vector<pair<short, short>>> parent;
  11. int n, m;
  12.  
  13. int BFS(const vector<vector<char>> &grid, const vector<vector<bool>> &blocked,
  14.         vector<vector<short>> &dist, vector<vector<pair<short, short>>> &parent)
  15. {
  16.     queue<pair<short, short>> q;
  17.     q.push({1, 1});
  18.     dist[1][1] = 0;
  19.     parent[1][1] = {-1, -1};
  20.  
  21.     int dx[] = {1, -1, 0, 0};
  22.     int dy[] = {0, 0, 1, -1};
  23.  
  24.     while (!q.empty())
  25.     {
  26.         auto [x, y] = q.front();
  27.         q.pop();
  28.  
  29.         if (x == n && y == m)
  30.             return dist[x][y];
  31.  
  32.         for (int d = 0; d < 4; d++)
  33.         {
  34.             int nx = x + dx[d];
  35.             int ny = y + dy[d];
  36.  
  37.             if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
  38.                 !blocked[nx][ny] && dist[nx][ny] == -1)
  39.             {
  40.                 dist[nx][ny] = dist[x][y] + 1;
  41.                 parent[nx][ny] = {x, y};
  42.                 q.push({nx, ny});
  43.             }
  44.         }
  45.     }
  46.  
  47.     return -1;
  48. }
  49.  
  50. int main(void)
  51. {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.     cout.tie(NULL);
  55.  
  56.     cin >> n >> m;
  57.  
  58.     vector<vector<char>> grid(n + 2, vector<char>(m + 2));
  59.     for (int i = 1; i <= n; i++)
  60.     {
  61.         for (int j = 1; j <= m; j++)
  62.         {
  63.             cin >> grid[i][j];
  64.         }
  65.     }
  66.  
  67.     vector<vector<bool>> blocked(n + 2, vector<bool>(m + 2, false));
  68.  
  69.     for (int i = 1; i <= n; i++)
  70.     {
  71.         for (int j = 1; j <= m; j++)
  72.         {
  73.             if (grid[i][j] != '.')
  74.             {
  75.                 blocked[i][j] = true;
  76.             }
  77.         }
  78.     }
  79.  
  80.     for (int i = 1; i <= n; i++)
  81.     {
  82.         for (int j = 1; j <= m; j++)
  83.         {
  84.             if (grid[i][j] == '^')
  85.             {
  86.                 for (int k = i - 1; k >= 1 && grid[k][j] == '.'; k--)
  87.                 {
  88.                     blocked[k][j] = true;
  89.                 }
  90.             }
  91.             else if (grid[i][j] == 'v')
  92.             {
  93.                 for (int k = i + 1; k <= n && grid[k][j] == '.'; k++)
  94.                 {
  95.                     blocked[k][j] = true;
  96.                 }
  97.             }
  98.             else if (grid[i][j] == '<')
  99.             {
  100.                 for (int k = j - 1; k >= 1 && grid[i][k] == '.'; k--)
  101.                 {
  102.                     blocked[i][k] = true;
  103.                 }
  104.             }
  105.             else if (grid[i][j] == '>')
  106.             {
  107.                 for (int k = j + 1; k <= m && grid[i][k] == '.'; k++)
  108.                 {
  109.                     blocked[i][k] = true;
  110.                 }
  111.             }
  112.         }
  113.     }
  114.  
  115.     if (blocked[1][1] || blocked[n][m])
  116.     {
  117.         cout << -1 << '\n';
  118.         return 0;
  119.     }
  120.  
  121.     dist.assign(n + 2, vector<short>(m + 2, -1));
  122.     parent.assign(n + 2, vector<pair<short, short>>(m + 2));
  123.  
  124.     int pathLength = BFS(grid, blocked, dist, parent);
  125.  
  126.     if (pathLength == -1)
  127.     {
  128.         cout << -1 << '\n';
  129.     }
  130.     else
  131.     {
  132.         vector<vector<char>> ans = grid;
  133.         int x = n, y = m;
  134.         while (x != -1 && y != -1)
  135.         {
  136.             if (ans[x][y] == '.')
  137.             {
  138.                 ans[x][y] = 'X';
  139.             }
  140.             auto [px, py] = parent[x][y];
  141.             x = px;
  142.             y = py;
  143.         }
  144.  
  145.         for (int i = 1; i <= n; i++)
  146.         {
  147.             for (int j = 1; j <= m; j++)
  148.             {
  149.                 cout << ans[i][j];
  150.             }
  151.             cout << '\n';
  152.         }
  153.     }
  154.  
  155.     return 0;
  156. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/F17NeV
language:
C++14 (gcc 8.3)
created:
3 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!