94pts/WA on 4#求助!
查看原帖
94pts/WA on 4#求助!
244309
yuhaocheng楼主2022/1/19 16:11
#include <bits/stdc++.h>
using namespace std;

const int maxn = 305;
const int dx[4] = { 0, 0,-1, 1};
const int dy[4] = {-1, 1, 0, 0};

int n, m;
char a[maxn][maxn];
int tox[maxn][maxn];
int toy[maxn][maxn];
int let2x[128];
int let2y[128];
int stx, sty;
int edx, edy;
int d[maxn][maxn];
int vis[maxn][maxn];

int bfs() {
	queue<pair<int, int> > q;
	q.push(pair<int, int>(stx, sty));
	d[stx][sty] = 0;
	while(!q.empty()) {
		if(vis[edx][edy]) {
			return d[edx][edy];
		}
		int fx = q.front().first;
		int fy = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++) {
			int tx = fx + dx[i];
			int ty = fy + dy[i];
			if(tx > n || tx < 1 || ty > m || ty < 1 || a[tx][ty] == '#') {
				continue;
			}
			if(vis[tx][ty]) {
				continue;
			}
			vis[tx][ty] = true;
			d[tx][ty] = d[fx][fy] + 1;
			if(tox[tx][ty] != 0) {
				d[tox[tx][ty]][toy[tx][ty]] = d[tx][ty];
				q.push(pair<int, int>(tox[tx][ty], toy[tx][ty]));
			} else {
				q.push(pair<int, int>(tx, ty));
			}
		}
	}
	return d[edx][edy];
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if(a[i][j] == '@') {
				stx = i;
				sty = j;
			} else if(a[i][j] == '=') {
				edx = i;
				edy = j;
			} else if(a[i][j] >= 'A' && a[i][j] <= 'Z') {
				if(let2x[a[i][j]] != 0) {
					tox[i][j] = let2x[a[i][j]];
					toy[i][j] = let2y[a[i][j]];
					tox[let2x[a[i][j]]][let2y[a[i][j]]] = i;
					toy[let2x[a[i][j]]][let2y[a[i][j]]] = j;
				} else {
					let2x[a[i][j]] = i;
					let2y[a[i][j]] = j;
				}
			}
		}
	}
	cout << bfs() << endl;
	// for(int i = 1; i <= n; i++) {
	// 	for(int j = 1; j <= m; j++) {
	// 		if(a[i][j] == '#') {
	// 			cout << "  #";
	// 		} else {
	// 			cout << right << setw(3) << d[i][j];
	// 		}
	// 	}
	// 	cout << endl;
	// }
}
2022/1/19 16:11
加载中...