Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- #include <string>
- #include <set>
- using namespace std;
- typedef long long ll;
- const ll INF = 1e9;
- #define pos pair<ll, ll>
- #define x first
- #define y second
- #define mp make_pair
- int main() {
- ll n, m;
- cin >> n >> m;
- vector<string> g(n);
- for (int i = 0; i < n; ++i) {
- cin >> g[i];
- }
- pos b; // стартовая вершина
- cin >> b.x >> b.y;
- b.x--, b.y--;
- pos e;
- cin >> e.x >> e.y;
- e.x--, e.y--;
- vector<vector<pos>> d(n, vector<pos>(m, pos(INF, 0)));
- d[b.x][b.y] = pos(0, 0);
- vector<vector<char>> u(n);
- set<pair<pos, pos>> q;
- q.insert(make_pair(d[b.x][b.y], b));
- while (!q.empty()) {
- pos v = q.begin()->second;
- q.erase(q.begin());
- if (g[v.x][v.y] == '+') {
- if (v.x > 0 && d[v.x][v.y].x + 1 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + 1;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + 1 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + 1;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + 1 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + 1;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + 1 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + 1;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //« - » означает, что этот блок имеет 2 двери — в соседний слева и соседний справа блок;
- if (g[v.x][v.y] == '-') {
- if (v.x > 0 && d[v.x][v.y].x + d[v.x][v.y].y % 2 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 2 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + d[v.x][v.y].y % 2 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 2 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //« | » означает, что этот блок имеет 2 двери — в соседний сверху и снизу блоки;
- if (g[v.x][v.y] == '|') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + d[v.x][v.y].y % 2 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + d[v.x][v.y].y % 2 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«^» означает, что этот блок имеет 1 дверь — в соседний сверху блок;
- if (g[v.x][v.y] == '^') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 3) % 4 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y) % 4 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 2) % 4 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«>» означает, что этот блок имеет 1 дверь — в соседний справа блок;
- if (g[v.x][v.y] == '>') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«v» означает, что этот блок имеет 1 дверь — в соседний снизу блок;
- if (g[v.x][v.y] == 'v') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 2) % 4 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 3) % 4 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 0) % 4 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«<» означает, что этот блок имеет 1 дверь — в соседний слева блок;
- if (g[v.x][v.y] == '<') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«L» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний слева блок;
- if (g[v.x][v.y] == 'L') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 == 0 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 == 0 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«R» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний справа блок;
- if (g[v.x][v.y] == 'R') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«U» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний сверху блок;
- if (g[v.x][v.y] == 'U') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 == 0 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 == 0 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- //«D» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний снизу блок;
- if (g[v.x][v.y] == 'D') {
- if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 == 0 < d[v.x - 1][v.y].x) {
- q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- d[v.x - 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 == 0;
- q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
- }
- if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x][v.y - 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x + 1][v.y].x) {
- q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
- q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
- }
- if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 0) % 4 == 0 < d[v.x][v.y + 1].x) {
- q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
- q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement