1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include <iostream> #include <queue> #include <cstdio> #include <cstring> using namespace std;
int n, m; char a[55][55]; int nextn[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int dis[55][55], vst[55][55];
struct Node { int x, y; };
int main() { cin >> n >> m; memset(a, 0, sizeof(a)); memset(dis, 0, sizeof(dis)); memset(vst, 0, sizeof(vst)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } queue<Node> que1; queue<Node> que2; que1.push(Node{1, 1}), dis[1][1] = 1, vst[1][1] = 1; que2.push(Node{n, m}), dis[n][m] = 1, vst[n][m] = 2; while (!que1.empty() && !que2.empty()) { int flag; Node head; if (que1.size() > que2.size()) { head = que2.front(); que2.pop(); flag = 2; } else { head = que1.front(); que1.pop(); flag = 1; } for (int i = 0; i < 4; i++) { int tx = head.x + nextn[i][0]; int ty = head.y + nextn[i][1]; if (tx > n || ty > m || tx <= 0 || ty <= 0) continue; if (a[tx][ty] == '.') { if (!dis[tx][ty]) { dis[tx][ty] = dis[head.x][head.y] + 1; vst[tx][ty] = vst[head.x][head.y]; if (flag == 1) que1.push(Node{tx, ty}); else if (flag == 2) que2.push(Node{tx, ty}); } else if (vst[head.x][head.y] + vst[tx][ty] == 3) { cout << dis[head.x][head.y] + dis[tx][ty] << endl; return 0; } } } }
return 0; }
|