Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define _test int _TEST; cin>>_TEST; while(_TEST--)
- #define pb push_back
- #define ff first
- #define ss second
- int main()
- {
- int n, m;
- cin>>n>>m;
- vector<string> s(n);
- for(auto &e: s) cin>>e;
- int sx, sy;
- int ex, ey;
- vector<vector<int>> blocked(n, vector<int> (n, 0));
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<n; j++)
- {
- if(s[i][j] == 'S')
- {
- sx = i;
- sy = j;
- }
- if(s[i][j] == 'G')
- {
- ex = i;
- ey = j;
- s[i][j] = '.';
- }
- if(s[i][j] == '<')
- {
- for(int k=j-1; k>=0; k--)
- {
- if(s[i][k] != '.') break;
- blocked[i][k] = 1;
- }
- }
- if(s[i][j] == '>')
- {
- for(int k=j+1; k<n; k++)
- {
- if(s[i][k] != '.') break;
- blocked[i][k] = 1;
- }
- }
- if(s[i][j] == '^')
- {
- for(int k=i-1; k>=0; k--)
- {
- if(s[k][j] != '.') break;
- blocked[k][j] = 1;
- }
- }
- if(s[i][j] == 'v')
- {
- for(int k=i+1; k<n; k++)
- {
- if(s[k][j] != '.') break;
- blocked[k][j] = 1;
- }
- }
- }
- }
- vector<vector<int>> vis(n, vector<int> (n, 0));
- vis[sx][sy] = 1;
- queue<pair<int, int>> qp;
- qp.push({sx, sy});
- while(qp.size())
- {
- auto e = qp.front();
- qp.pop();
- int i = e.ff;
- int j = e.ss;
- int c = vis[i][j];
- if(i-1>=0 && !vis[i-1][j] && s[i-1][j]=='.' && !blocked[i-1][j])
- vis[i-1][j]=c+1, qp.push({i-1, j});
- if(i+1<n && !vis[i+1][j] && s[i+1][j]=='.' && !blocked[i+1][j])
- vis[i+1][j]=c+1, qp.push({i+1, j});
- if(j-1>=0 && !vis[i][j-1] && s[i][j-1]=='.' && !blocked[i][j-1])
- vis[i][j-1]=c+1, qp.push({i, j-1});
- if(j+1<n && !vis[i][j+1] && s[i][j+1]=='.' && !blocked[i][j+1])
- vis[i][j+1]=c+1, qp.push({i, j+1});
- }
- cout<<vis[ex][ey] - 1<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment