Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- struct Point
- {
- int i, j;
- };
- int n, m;
- const int INF = (int)1e9;
- bool can(Point p)
- {
- return 0 <= p.i && 0 <= p.j && p.i < n && p.j < m;
- }
- main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n >> m;
- vector<vector<bool>> p(n, vector<bool>(m));
- Point start, finish;
- for(int i = 0; i < n; i++)
- {
- string s;
- cin >> s;
- for(int j = 0; j < m; j++)
- {
- if(s[j] == 'S')
- start = {i, j}, p[i][j] = true;
- if(s[j] == 'F')
- finish = {i, j}, p[i][j] = true;
- if(s[j] == '.')
- p[i][j] = true;
- }
- }
- queue<Point> q;
- q.push(start);
- vector<vector<int>> dp(n, vector<int>(m, INF));
- vector<vector<bool>> vis(n, vector<bool> (m, false));
- dp[start.i][start.j] = 0;
- while(!q.empty())
- {
- Point cur = q.front();
- q.pop();
- vis[cur.i][cur.j] = true;
- for(int i = 1; ; i++)
- {
- Point next = {cur.i + i, cur.j};
- if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
- {
- dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
- q.push(next);
- }
- else
- break;
- }
- for(int i = -1; ; i--)
- {
- Point next = {cur.i + i, cur.j};
- if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
- {
- dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
- q.push(next);
- }
- else
- break;
- }
- for(int j = 1; ; j++)
- {
- Point next = {cur.i, cur.j + j};
- if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
- {
- dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
- q.push(next);
- }
- else
- break;
- }
- for(int j = -1; ; j--)
- {
- Point next = {cur.i, cur.j + j};
- if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
- {
- dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
- q.push(next);
- }
- else
- break;
- }
- }
- if(dp[finish.i][finish.j] == INF)
- cout << -1;
- else
- cout << dp[finish.i][finish.j];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement