94 分,WA on #11,求助大佬
查看原帖
94 分,WA on #11,求助大佬
421781
liuzimingc楼主2021/8/2 22:03

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

求助各位大佬!

2021/8/2 22:03
加载中...