Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <set>
- #include <cmath>
- #include <map>
- #include <queue>
- #include <iomanip>
- #include <cstdlib>
- #include <stdio.h>
- #include <ctime>
- #include <stack>
- #include <cmath>
- #include <sstream>
- #include <iostream>
- #include <unordered_map>
- #include <functional>
- #define X first
- #define Y second
- #define mp make_pair
- #define All(x) (x).begin(),(x).end()
- #define f_in freopen("input.txt", "r", stdin)
- #define f_out freopen("output.txt", "w", stdout)
- #define file_on f_in; f_out
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- using namespace std;
- const ll linf = 10000000000000043;
- const int inf = 1000000043;
- using namespace std;
- char a[1010][1010];
- int mas[1010][1010];
- /*
- < -1
- ^ 2
- > 1
- -2
- */
- void rec(int q, int x, int y)
- {
- //cout << x << y << endl;
- if (a[x - 1][y] != '*')
- {
- int pre = mas[x - 1][y];
- if (q == 2) mas[x - 1][y] = min(mas[x][y],mas[x-1][y]);
- else mas[x - 1][y] = min(mas[x][y]+1, mas[x - 1][y]);
- if (pre > mas[x - 1][y]) rec(2, x - 1, y);
- }
- if (a[x + 1][y] != '*')
- {
- int pre = mas[x + 1][y];
- if (q == -2) mas[x + 1][y] = min(mas[x][y], mas[x + 1][y]);
- else mas[x + 1][y] = min(mas[x][y] + 1, mas[x + 1][y]);
- if (pre > mas[x + 1][y]) rec(-2, x + 1, y);
- }
- if (a[x][y-1] != '*')
- {
- int pre = mas[x][y-1];
- if (q == -1) mas[x][y-1] = min(mas[x][y], mas[x][y-1]);
- else mas[x][y-1] = min(mas[x][y] + 1, mas[x ][y-1]);
- if (pre > mas[x][y-1]) rec(-1, x, y - 1);
- }
- if (a[x][y + 1] != '*')
- {
- int pre = mas[x][y+1];
- if (q == 1) mas[x][y + 1] = min(mas[x][y], mas[x][y + 1]);
- else mas[x][y + 1] = min(mas[x][y] + 1, mas[x][y + 1]);
- if (pre > mas[x][y+1]) rec(1, x, y + 1);
- }
- }
- int main()
- {
- for (int i = 0; i <= 1001; i++)
- for (int j = 0; j <= 1001; j++)
- a[i][j] = '*',mas[i][j]=inf;
- int n, m, x1, y1, x2, y2;
- cin >> n >> m;
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- char c;
- cin >> c;
- if (c == 'T') x2 = i, y2 = j;
- if (c == 'S') x1 = i, y1 = j;
- a[i][j] = c;
- }
- }
- mas[x1][y1] = 0;
- if (a[x1 - 1][y1] != '*') rec(2, x1, y1);
- if (a[x1 + 1][y1] != '*') rec(-2, x1, y1);
- if (a[x1][y1+1] != '*') rec(1, x1, y1);
- if (a[x1][y1-1] != '*') rec(-1, x1, y1);
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- cout << mas[i][j] << ' ';
- cout << endl;
- }
- if (mas[x2][y2] > 2) cout << "NO" << endl;
- else cout << "YES" << endl;
- }
- /*
- 4 4
- S.*.
- ..*.
- ..*.
- *..T
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement