94pts WA#4求条
查看原帖
94pts WA#4求条
1112305
Alpha1115楼主2025/2/7 16:10
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char mp[305][305];
int num(int x, int y) {
	return x * 1000 + y;
}
int fst[35];
int cs[400005];
bool vis[305][305];
struct Node{
	int x, y, dis, f;
};
queue <Node> q;
void bfs() {
	vis[sx][sy] = 1;
	q.push({sx, sy, 0, 0});
	while (!q.empty()) {
		Node hd = q.front();
		q.pop();
		int x = hd.x, y = hd.y, dis = hd.dis, f = hd.f;
		//cout << x << " " << y << " " << dis << " " << f << endl;
		if (mp[x][y] == '=') {
			cout << dis;
			return;
		}
		if (isalpha(mp[x][y]) && !f) {
			int nx = cs[num(x, y)] / 1000, ny = cs[num(x, y)] % 1000;
			q.push({nx, ny, dis, 1});
			continue;
		}
		for (int i = 0; i < 4; i ++) {
			int nx = x + d[i][0], ny = y + d[i][1];
			if (nx < 1 || ny < 1 || nx > n || ny > m || mp[nx][ny] == '#' || vis[nx][ny]) continue;
			vis[nx][ny] = 1;
			q.push({nx, ny, dis + 1, 0});
 		}
	}
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)	
		for (int j = 1; j <= m; j ++) {
			cin >> mp[i][j];
			if (isalpha(mp[i][j])) {
				if (fst[mp[i][j] - 'A' + 1]) cs[num(i, j)] = fst[mp[i][j] - 'A' + 1], cs[fst[mp[i][j] - 'A' + 1]] = num(i, j);
				else fst[mp[i][j] - 'A' + 1] = num(i, j);
			}
			if (mp[i][j] == '@') sx = i, sy = j;
		}
	bfs();
}

2025/2/7 16:10
加载中...