正经题解|地宫2
2024-03-22 11:18:52
发布于:浙江
9阅读
0回复
0点赞
【算法分析】
从左上角开始广搜,计算走到右下角需要的步数。这题有传送阵的概念,而且传送不需要花费步数。队列里的元素是按照步数排序的,因此需要考虑什么时候将传送阵放进队列中。应该是当搜到任意一个传送阵的时候将所有传送阵放进队列,因为到达它们所需要的步数是一样的,这样就能保证队列里的元素的步数是非降的。
【参考代码】
#include<bits/stdc++.h>
using namespace std;
char MAP[49][49];
struct node {
int x, y, step;
}l,r;
bool vis[49][49];
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };
int main() {
int R, C;
cin >> R >> C;
vector<node> transfer;
for (int i = 1; i <= R; i++) {
cin >> MAP[i] + 1;
for (int j = 1; j <= C; j++) {
if (MAP[i][j] == '$') {
transfer.push_back({ i,j,0});
}
}
}
queue<node> q;
q.push({ 1,1,0 });
vis[1][1] = 1;
while (q.size()) {
r = q.front();
q.pop();
if (r.x == R && r.y == C) {
cout << r.step + 1;
break;
}
for (int i = 0; i < 4; i++) {
l.x = r.x + dir[i][0], l.y = r.y + dir[i][1], l.step = r.step + 1;
if (l.x >= 1 && l.x <= R && l.y >= 1 && l.y <= C && !vis[l.x][l.y] && MAP[l.x][l.y] != '#') {
q.push(l);
vis[l.x][l.y] = 1;
if (MAP[l.x][l.y] == '$') {
for (int i = 0; i < transfer.size(); i++) {
if (vis[transfer[i].x][transfer[i].y]) continue;
l.x = transfer[i].x, l.y = transfer[i].y, l.step = r.step + 1;
q.push(l);
vis[l.x][l.y] = 1;
}
}
}
}
}
if (!vis[R][C]) cout << -1;
return 0;
}
【时间复杂度】
【预计得分】
这里空空如也
有帮助,赞一个