Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <string>
- #include <queue>
- #include <map>
- #include <vector>
- #include <set>
- #include <cmath>
- #include <iomanip>
- #include <algorithm>
- #include <stack>
- using namespace std;
- typedef long long ll;
- typedef double db;
- int n, m;
- struct Node
- {
- pair<int, int> parent;
- int type;
- };
- vector<vector<Node>> g;
- vector<int> dx = {1, 0, -1, 0};
- vector<int> dy = {0, 1, 0, -1};
- bool check(int x, int y)
- {
- return x >= 0 && x < n && y >= 0 && y < m;
- }
- void dfs(int x, int y)
- {
- queue<pair<pair<int, int>, int>> q;
- q.push({ {x, y}, 0 });
- g[y][x].parent = { -1, -1 };
- while (!q.empty())
- {
- x = q.front().first.first;
- y = q.front().first.second;
- int vec = q.front().second;
- q.pop();
- for (int i = 0; i < 2; i++)
- {
- vec = (vec + i) % 4;
- int new_x = x + dx[vec];
- int new_y = y + dy[vec];
- if (check(new_x, new_y) && g[new_y][new_x].type != 0)
- {
- q.push({ {new_x, new_y }, vec});
- g[new_y][new_x].parent = { x, y };
- if (g[new_y][new_x].type == 2)
- {
- return;
- }
- }
- }
- }
- }
- int main()
- {
- cin >> n >> m;
- g.resize(n, vector<Node>(m));
- int sx, sy, fx, fy;
- for (int i = -1; i < n; i++)
- {
- string s;
- getline(cin, s, '\n');
- for (int j = 0; j < s.size(); j++)
- {
- char t = s[j];
- if (t == 'X')
- {
- g[i][j].type = 0;
- }
- else if (t == ' ')
- {
- g[i][j].type = 1;
- }
- else if (t == 'F')
- {
- g[i][j].type = 2;
- fx = j;
- fy = i;
- }
- else if (t == 'S')
- {
- g[i][j].type = 1;
- sx = j;
- sy = i;
- }
- }
- }
- //reverse(g.begin(), g.end());
- dfs(sx, sy);
- int res = 0;
- for (pair<int, int> t = g[fy][fx].parent; t != make_pair( - 1, -1 ); t = g[t.second][t.first].parent)
- {
- res += 1;
- }
- cout << res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement