正经题解｜地宫2
2024-03-22 11:18:52
发布于：浙江
23阅读
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;
}
【时间复杂度】
【预计得分】
全部评论 1
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
谢谢AC君的题解，AC啦
#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; }2024-08-04 来自 北京
0
有帮助，赞一个