88分求调
查看原帖
88分求调
1401095
zhangchengqi666楼主2025/1/14 19:40

88分求调(第一个点MLE,朴素的BFS做法)88分求调(第一个点MLE,朴素的BFS做法)
包关注的包关注的
其实是我自己交了20多次还没做出来

#include <bits/stdc++.h>

using namespace std;

int mp[11][11], dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int n, m, sx, sy, fx, fy, ans = 0x7f7f7f7f, mx, my;

queue<pair<pair<int, int> , pair<int, int> > > q;

void bfs(int x, int y, int z, int cnt) {
	q.push(make_pair(make_pair(x, y), make_pair(z, cnt)));
	while (!q.empty()) {
		int tx = q.front().first.first;
		int ty = q.front().first.second;
		int& mou = q.front().second.first;
		int step = q.front().second.second;
		if (mou == 0 || step > ans || step > m * n) {
			q.pop();
			continue;
		}
		if (mp[tx][ty] == 4) {
			mou = 6;
		}
		if (tx == fx && ty == fy) {
			ans = min(ans, step);
			q.pop();
			continue;
		}
		for (int i = 0; i < 4; i++) {
			int mx = tx + dx[i];
			int my = ty + dy[i];
			if (mx < 1 || my < 1 || mx > n || my > m || mp[mx][my] == 0) {
				continue;
			}
			q.push(make_pair(make_pair(mx, my), make_pair(mou - 1, step + 1)));
		}
		q.pop();
	}
	return;
}

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mp[i][j];
			if (mp[i][j] == 2) {
				sx = i, sy = j;
			}
			if (mp[i][j] == 3) {
				fx = i, fy = j;
			}
		}
	}
	bfs(sx, sy, 6, 0);
	if (ans == 0x7f7f7f7f) {
		cout << -1;
	} else cout << ans;
	return 0;
}
2025/1/14 19:40
加载中...