Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define ld long double
- #define inf LONG_MAX
- using namespace std;
- struct two
- {
- ll x, y;
- };
- char board[1000][1000];
- ll dst[1000][1000];
- ll n, m, startX, startY, finishX, finishY;
- bool can(ll a, ll b)
- {
- return a < n && a >= 0 && b >= 0 && b < m;
- }
- vector <two> tp;
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- cin >> n >> m;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- {
- cin >> board[i][j];
- if (board[i][j] == 'T')
- tp.push_back({i, j});
- dst[i][j] = inf;
- }
- cin >> startX >> startY >> finishX >> finishY;
- startX--;
- startY--;
- finishX--;
- finishY--;
- queue <two> q;
- dst[startX][startY] = 0;
- q.push({startX, startY});
- while (!q.empty())
- {
- two cur = q.front();
- q.pop();
- if (can(cur.x + 1, cur.y) && dst[cur.x][cur.y] + 1 < dst[cur.x + 1][cur.y])
- {
- q.push({cur.x + 1, cur.y});
- dst[cur.x + 1][cur.y] = dst[cur.x][cur.y] + 1;
- }
- if (can(cur.x - 1, cur.y) && dst[cur.x][cur.y] + 1 < dst[cur.x - 1][cur.y])
- {
- q.push({cur.x - 1, cur.y});
- dst[cur.x - 1][cur.y] = dst[cur.x][cur.y] + 1;
- }
- //
- if (can(cur.x, cur.y + 1) && dst[cur.x][cur.y] + 1 < dst[cur.x][cur.y + 1])
- {
- q.push({cur.x, cur.y + 1});
- dst[cur.x][cur.y + 1] = dst[cur.x][cur.y] + 1;
- }
- if (can(cur.x, cur.y - 1) && dst[cur.x][cur.y] + 1 < dst[cur.x][cur.y - 1])
- {
- q.push({cur.x, cur.y - 1});
- dst[cur.x][cur.y - 1] = dst[cur.x][cur.y] + 1;
- }
- if (board[cur.x][cur.y] == 'T')
- for (auto c : tp)
- if (dst[cur.x][cur.y] < dst[c.x][c.y])
- {
- q.push(c);
- dst[c.x][c.y] = dst[cur.x][cur.y];
- }
- }
- if (dst[finishX][finishY] == inf)
- dst[finishX][finishY] = -1;
- cout << dst[finishX][finishY];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement