fork download
copy 
  1. // author:  anil_1
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. class Cell {
  8. public:
  9.     int row, col, jumps;
  10.     bool r = false, c = false;
  11.     Cell(int _row, int _col, int _jumps, bool _r, bool _c): 
  12.         row{_row}, col{_col}, jumps{_jumps}, r{_r}, c{_c} {
  13.  
  14.     }
  15.     void debug() {
  16.         cout << row << ' ' << col << ' ' << r << ' ' << c << ' ' << jumps << '\n';
  17.     }
  18. };
  19.  
  20.  
  21. int getMinJumps(vector<string>& grid) {
  22.     int n = grid.size(), m = grid[0].size();
  23.     int rs = -1, cs = -1;
  24.     for(int i = 0; i < n; i++) {
  25.         for(int j = 0; i < m; j++) {
  26.             if(grid[i][j] == 'S') {
  27.                 rs = i, cs = j;
  28.                 break;
  29.             }
  30.         }
  31.         if(rs != -1) break;
  32.     }
  33.     grid[rs][cs] = '*';
  34.     queue<Cell> q;
  35.     vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(4, 1 << 30)));
  36.     vector<vector<vector<bool>>> seen(n, vector<vector<bool>>(m, vector<bool>(4)));
  37.     for(int i = 0; i < n; i++) {
  38.         for(int j = 0; j < m; j++) {   
  39.             if(grid[i][j] == 'E') {
  40.                 q.push(Cell(i, j, 0, true, true));
  41.                 dp[i][j][1] = dp[i][j][3] = 0;
  42.                 seen[i][j][1] = seen[i][j][3] = true;
  43.                 break;
  44.             }
  45.         }
  46.     }
  47.     //{row, row-1, col, col - 1}
  48.     while(!q.empty()) {
  49.         Cell c = q.front();
  50.         // c.debug();
  51.         q.pop();
  52.  
  53.         if(c.c) {
  54.             if(c.row - 1 >= 0 && !seen[c.row - 1][c.col][1] && grid[c.row - 1][c.col] == '*'
  55.                 && dp[c.row - 1][c.col][1] >= c.jumps + 1) {
  56.                 // push to queue
  57.                 q.push(Cell(c.row - 1, c.col, c.jumps + 1, true, false));
  58.                 dp[c.row - 1][c.col][1] = c.jumps + 1;
  59.                 seen[c.row - 1][c.col][1] = true;
  60.             }
  61.             if(c.row + 1 < n && !seen[c.row + 1][c.col][1] && grid[c.row + 1][c.col] == '*'
  62.                 && dp[c.row + 1][c.col][1] >= c.jumps + 1) {
  63.                 // push to queue
  64.                 q.push(Cell(c.row + 1, c.col, c.jumps + 1, true, false));
  65.                 dp[c.row + 1][c.col][1] = c.jumps + 1;
  66.                 seen[c.row + 1][c.col][1] = true;
  67.             }
  68.         } else {
  69.             // cover whole col
  70.             for(int i = 0; i < n; i++) {
  71.                 if(i == c.row or grid[i][c.col] != '*' or seen[i][c.col][1]
  72.                     or dp[i][c.col][1] < c.jumps + 1) continue;
  73.                 // push to queue
  74.                 q.push(Cell(i, c.col, c.jumps + 1, true, false));
  75.                 dp[i][c.col][1] = c.jumps + 1;
  76.                 seen[i][c.col][1] = true;
  77.             }
  78.         }
  79.  
  80.         if(c.r) {
  81.             if(c.col - 1 >= 0 && !seen[c.row][c.col - 1][3] && grid[c.row][c.col - 1] == '*'
  82.                 && dp[c.row][c.col - 1][3] >= c.jumps + 1) {
  83.                 // push to queue
  84.                 q.push(Cell(c.row, c.col - 1, c.jumps + 1, false, true));
  85.                 dp[c.row][c.col - 1][3] = c.jumps + 1;
  86.                 seen[c.row][c.col - 1][3] = true;
  87.             }
  88.             if(c.col + 1 < m && !seen[c.row][c.col + 1][3] && grid[c.row][c.col + 1] == '*'
  89.                 && dp[c.row][c.col + 1][3] >= c.jumps + 1) {
  90.                 // push to queue
  91.                 q.push(Cell(c.row, c.col + 1, c.jumps + 1, false, true));
  92.                 dp[c.row][c.col + 1][3] = c.jumps + 1;
  93.                 seen[c.row][c.col + 1][3] = true;
  94.             }
  95.         } else {
  96.             // cover whole row
  97.             for(int j = 0; j < m; j++) {
  98.                 if(j == c.col or grid[c.row][j] != '*' or seen[c.row][j][3]
  99.                     or dp[c.row][j][3] < c.jumps + 1) continue;
  100.                 // push to queue
  101.                 q.push(Cell(c.row, j, c.jumps + 1, false, true));
  102.                 dp[c.row][j][1] = c.jumps + 1;
  103.                 seen[c.row][j][3] = true;
  104.             }
  105.         }
  106.     }
  107.     int ans = *min_element(dp[rs][cs].begin(), dp[rs][cs].end());
  108.     if(ans == (1 << 30)) ans = -1;
  109.     return ans;
  110. }
  111.  
  112. int main() {
  113.     ios_base::sync_with_stdio(false);
  114.     cin.tie(nullptr);
  115.     vector<string> grid = {
  116.         "S****#", 
  117.         "**#***", 
  118.         "*****#", 
  119.         "#****E"
  120.     };
  121.     cout << getMinJumps(grid) << '\n';
  122.     grid = {
  123.         "S******", 
  124.         "#######", 
  125.         "######*", 
  126.         "######E"
  127.     };
  128.     cout << getMinJumps(grid) << '\n';
  129.     grid = {
  130.         "S#", 
  131.         "#E"
  132.     };
  133.     cout << getMinJumps(grid) << '\n';
  134.     grid = {
  135.         "S#**", 
  136.         "#E**"
  137.     }; // answer should be 4 for this
  138.     cout << getMinJumps(grid) << '\n';
  139.     return 0;
  140. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
4
-1
4
https://ideone.com/sqnylK
language:
C++14 (gcc 8.3)
created:
7 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!