Ankit_132

E

Aug 27th, 2023
249
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll     long long
  6. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  7. #define pb     push_back
  8. #define ff     first
  9. #define ss     second
  10.  
  11. int main()
  12. {
  13.     int n, m;
  14.     cin>>n>>m;
  15.  
  16.     vector<string> s(n);
  17.     for(auto &e: s)   cin>>e;
  18.    
  19.     int sx, sy;
  20.     int ex, ey;
  21.  
  22.     vector<vector<int>> blocked(n, vector<int> (n, 0));
  23.  
  24.     for(int i=0; i<n; i++)
  25.     {
  26.         for(int j=0; j<n; j++)
  27.         {
  28.             if(s[i][j] == 'S')
  29.             {
  30.                 sx = i;
  31.                 sy = j;
  32.             }
  33.  
  34.             if(s[i][j] == 'G')
  35.             {
  36.                 ex = i;
  37.                 ey = j;
  38.                 s[i][j] = '.';
  39.             }
  40.  
  41.             if(s[i][j] == '<')
  42.             {
  43.                 for(int k=j-1; k>=0; k--)
  44.                 {
  45.                     if(s[i][k] != '.')      break;
  46.                     blocked[i][k] = 1;
  47.                 }
  48.             }
  49.  
  50.             if(s[i][j] == '>')
  51.             {
  52.                 for(int k=j+1; k<n; k++)
  53.                 {
  54.                     if(s[i][k] != '.')      break;
  55.                     blocked[i][k] = 1;
  56.                 }
  57.             }
  58.  
  59.             if(s[i][j] == '^')
  60.             {
  61.                 for(int k=i-1; k>=0; k--)
  62.                 {
  63.                     if(s[k][j] != '.')      break;
  64.                     blocked[k][j] = 1;
  65.                 }
  66.             }
  67.  
  68.             if(s[i][j] == 'v')
  69.             {
  70.                 for(int k=i+1; k<n; k++)
  71.                 {
  72.                     if(s[k][j] != '.')      break;
  73.                     blocked[k][j] = 1;
  74.                 }
  75.             }
  76.         }
  77.     }
  78.  
  79.     vector<vector<int>> vis(n, vector<int> (n, 0));
  80.     vis[sx][sy] = 1;
  81.  
  82.     queue<pair<int, int>> qp;
  83.     qp.push({sx, sy});
  84.  
  85.     while(qp.size())
  86.     {
  87.         auto e = qp.front();
  88.         qp.pop();
  89.  
  90.         int i = e.ff;
  91.         int j = e.ss;
  92.         int c = vis[i][j];
  93.  
  94.         if(i-1>=0 && !vis[i-1][j] && s[i-1][j]=='.' && !blocked[i-1][j])
  95.             vis[i-1][j]=c+1, qp.push({i-1, j});
  96.         if(i+1<n && !vis[i+1][j] && s[i+1][j]=='.' && !blocked[i+1][j])
  97.             vis[i+1][j]=c+1, qp.push({i+1, j});
  98.         if(j-1>=0 && !vis[i][j-1] && s[i][j-1]=='.' && !blocked[i][j-1])
  99.             vis[i][j-1]=c+1, qp.push({i, j-1});
  100.         if(j+1<n && !vis[i][j+1] && s[i][j+1]=='.' && !blocked[i][j+1])
  101.             vis[i][j+1]=c+1, qp.push({i, j+1});
  102.     }
  103.  
  104.     cout<<vis[ex][ey] - 1<<"\n";
  105. }
  106.  
Advertisement
Add Comment
Please, Sign In to add comment