社区讨论

93分,wa最后一个点

P1825[USACO11OPEN] Corn Maze S参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m2bwnyw6
此快照首次捕获于
2024/10/16 21:26
去年
此快照最后确认于
2025/11/04 17:02
4 个月前
查看原帖
CPP
#include <queue>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
char a[N][N];
int n, m, dis[N][N], st[N][N];
int walk[4][2] = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
queue<PII> q;
struct node {
	int x1 = 0;
	int y1 = 0;
	int x2 = 0;
	int y2 = 0;
}tran[100];
bool in(int x, int y) {
	return x >= 1 && y >= 1 && x <= n && y <= m;
}
int bfs() {
	while(!q.empty()) {
		PII t = q.front();
		if(a[t.first][t.second] == '=') {
			return dis[t.first][t.second];
		}
		q.pop();
		for(int i = 0; i < 4; i++) {
			int dx = t.first + walk[i][0];
			int dy = t.second + walk[i][1];
			if(a[dx][dy] != '#' && in(dx, dy) && !(a[dx][dy] >= 'A' && a[dx][dy] <= 'Z') && st[dx][dy] == 0) {
				dis[dx][dy] = dis[t.first][t.second] + 1;
				q.push({dx, dy});
				st[dx][dy] = 1;
			}
			if(a[dx][dy] >= 'A' && a[dx][dy] <= 'Z') {
				int ddx = 0, ddy = 0;
				char c = a[dx][dy];
				if(tran[c].x1 == dx && tran[c].y1 == dy) {
					ddx = tran[c].x2;
					ddy = tran[c].y2;
				}else {
					ddx = tran[c].x1;
					ddy = tran[c].y1;
				}
				dis[ddx][ddy] = dis[t.first][t.second] + 1;
				q.push({ddx, ddy});
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(a[i][j] == '@') {
				q.push({i, j});
				st[i][j] = 1;
			}
			if(a[i][j] >= 'A' && a[i][j] <= 'Z') {
				if(tran[a[i][j]].x1 == 0) {
					tran[a[i][j]].x1 = i;
					tran[a[i][j]].y1 = j;
				}else {
					tran[a[i][j]].x2 = i;
					tran[a[i][j]].y2 = j;
				}
			}
		}
	}
	cout << bfs();
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...