38pts求调
查看原帖
38pts求调
602624
___njr___楼主2023/6/16 21:55
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
const int N = 310;

int n, m;
int end_x, end_y, sta_x, sta_y;
// 坐标位移
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

char g[N][N];    // 存原始地图
int d[N][N];    // 存每个点到起始点的距离
int ghuansong[N * N];
int bfs() {
	queue<PII> q;
	PII t = {sta_x, sta_y};
	q.push(t);

	while (!q.empty()) {
		auto pp = q.front();
		q.pop();
		if (ghuansong[pp.first * N + pp.second]) {
			d[ghuansong[pp.first * N + pp.second] / N][ ghuansong[pp.first * N + pp.second] % N] = d[pp.first][pp.second] + 1;
			q.push({ghuansong[pp.first * N + pp.second] / N, ghuansong[pp.first * N + pp.second] % N});
		}
		if (pp.first == end_x && pp.second == end_y) break;
//		cout << pp.first << ' ' << pp.second << ' ' << d[pp.first][pp.second] << endl;
		for (int i = 0; i < 4; i++) {
			int x = pp.first + dx[i];
			int y = pp.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] ^ '#' && d[x][y] == -1) {
				// 记录答案
				d[x][y] = d[pp.first][pp.second] + 1;
				// 扩展队头
				q.push({x, y});
			}
		}
	}

	return d[end_x][end_y] - 1;
}

int tmp[128];
int main() {
	cin >> n >> m;
	// 读入地图
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
			if (g[i][j] >= 'A' && g[i][j] <= 'Z') {
				if (tmp[g[i][j]]) {
					ghuansong[tmp[g[i][j]]] = i * N + j;
					ghuansong[i * N + j] = tmp[g[i][j]];
				} else tmp[g[i][j]] = i * N + j;
			} else if (g[i][j] == '=')end_x = i, end_y = j;
			else if (g[i][j] == '@')sta_x = i, sta_y = j;
		}

	// 初始化
	memset(d, -1, sizeof(d));
	d[sta_x][sta_y] = 0;

	cout << bfs() << endl;
	return 0;
}
2023/6/16 21:55
加载中...