RT。代码如下:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const int walk[5][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}};
int n, m, xa, ya, xb, yb;
string t;
char a[MAXN][MAXN];
bool vis[MAXN][MAXN];
int to[27][4], ts[27];
struct node {
int x, y, t;
bool flag;
};
queue<node> Q;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
getline(cin, t);
for (int j = 1; j <= m; j++) {
a[i][j] = getchar();
if (a[i][j] == '@') xa = i, ya = j;
if (a[i][j] == '=') xb = i, yb = j;
if ('A' <= a[i][j] && a[i][j] <= 'Z') {
int k = a[i][j] - 'A';
if (!ts[k]) {
to[k][0] = i; to[k][1] = j;
ts[k]++;
}
else to[k][2] = i, to[k][3] = j;
}
}
}
vis[xa][ya] = true;
Q.push((node){xa, ya, 0, true});
while (!Q.empty()) {
node u = Q.front();
Q.pop();
if (u.x == xb && u.y == yb) {
cout << u.t << endl;
return 0;
}
int x = u.x, y = u.y;
if ('A' <= a[x][y] && a[x][y] <= 'Z' && u.flag) {
int k = a[x][y] - 'A';
if (x == to[k][0] && y == to[k][1]) x = to[k][2], y = to[k][3];
else x = to[k][0], y = to[k][1];
Q.push((node){x, y, u.t, false});
continue;
}
for (int i = 0; i < 4; i++) {
int x = u.x + walk[i][0], y = u.y + walk[i][1];
if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '#' || vis[x][y]) continue;
Q.push((node){x, y, u.t + 1, true});
vis[x][y] = true;
}
}
puts("-1");
return 0;
}
样例输入:
30 16
##############=#
#A...........A.#
#.B...........B#
#C...........C.#
#.D...........D#
#E...........E.#
#.F...........F#
#G...........G.#
#.H...........H#
#I...........I.#
#.J...........J#
#K...........K.#
#.L...........L#
#M...........M.#
#.N...........N#
#O...........O.#
#.P...........P#
#Q...........Q.#
#.R...........R#
#S...........S.#
#.T...........T#
#U...........U.#
#.V...........V#
#W...........W.#
#.X...........X#
#Y...........Y.#
#.Z...........Z#
#.##############
#.............@#
################
样例输出:42
我的输出:44
求助各位大佬!