Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <cstdio>
- #include <algorithm>
- #include <iostream>
- #include <string>
- #include <string.h>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <math.h>
- #include <cmath>
- #include <map>
- #include <set>
- #include <cstdlib>
- #include <utility>
- #include <iomanip>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef string st;
- typedef pair<int, int> pii;
- typedef vector <pair<int, int>> vpii;
- struct ver {
- int xv, yv;
- bool h;
- };
- const int INF = 1e5;
- const int SIZE = 501;
- char g[SIZE][SIZE];
- int used[SIZE][SIZE], dist[SIZE][SIZE], n, m;
- pii par[SIZE][SIZE];
- deque<ver> q;
- bool exist(int x1, int y1) {
- return !(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m);
- }
- int dx[] = { 1, -1, 0, 0 };
- int dy[] = { 0, 0, -1, 1 };
- int size_d = 4;
- int main() {
- //setlocale(LC_ALL, "Russian");
- //freopen("INPUT.TXT", "r", stdin);
- //freopen("OUTPUT.TXT", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cin >> n >> m;
- int xc, yc;
- int xl, yl;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- cin >> g[i][j];
- if (g[i][j] == 'F') {
- xc = i;
- yc = j;
- }
- if (g[i][j] == 'S') {
- xl = i;
- yl = j;
- }
- if (g[i][j] == 'P') used[i][j] = 1;
- dist[i][j] = INF;
- }
- }
- used[xc][yc] = 1;
- dist[xc][yc] = 0;
- //par[xc][yc] = make_pair(-1, -1);
- q.push_back({ xc, yc, 1 });
- while (!q.empty()) {
- int x = q.front().xv;
- int y = q.front().yv;
- bool h = q.front().h;
- q.pop_front();
- if (h) {
- int tox = x;
- for (int toy = y + 1; toy < n; toy++) {
- if (g[tox][toy] == 'P') break;
- else if (exist(tox, toy) && !used[tox][toy]) {
- used[tox][toy] = 1;
- dist[tox][toy] = dist[x][y] + 1;
- par[tox][toy] = make_pair(x, y);
- q.push_back({ tox, toy, 0 });
- }
- }
- for (int toy = 0; toy < y; toy++) {
- if (g[tox][toy] == 'P') break;
- else if (exist(tox, toy) && !used[tox][toy]) {
- used[tox][toy] = 1;
- dist[tox][toy] = dist[x][y] + 1;
- par[tox][toy] = make_pair(x, y);
- q.push_front({ tox, toy, 0 });
- }
- }
- }
- if(!h || x==xc && y==yc) {
- int toy = y;
- for (int tox = x + 1; tox < m; tox++) {
- if (g[tox][toy] == 'P') break;
- else if (exist(tox, toy) && !used[tox][toy]) {
- used[tox][toy] = 1;
- dist[tox][toy] = dist[x][y] + 1;
- par[tox][toy] = make_pair(x, y);
- q.push_back({ tox, toy, 1 });
- }
- }
- for (int tox = 0; tox < x; tox++) {
- if (g[tox][toy] == 'P') break;
- else if (exist(tox, toy) && !used[tox][toy]) {
- used[tox][toy] = 1;
- dist[tox][toy] = dist[x][y] + 1;
- par[tox][toy] = make_pair(x, y);
- q.push_front({ tox, toy, 1 });
- }
- }
- }
- }
- cout << dist[xl][yl];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement