牛客小白月赛26 E 牛牛走迷宫
牛牛走迷宫
https://ac.nowcoder.com/acm/contest/6013/E
Description
牛牛周末去了游乐园走迷宫。这是一个n*m大小的01迷宫，0表示这个位置可以走，1表示有障碍物不能。
走。现在牛牛在起点(1,1),他想要走到终点(n,m)。并且，如果他能够走到终点的话，他想要知道自己是怎么走到终点的。
如果可以走到终点，因为牛牛比较懒他会先保证走的步数最少，又因为牛牛是个追求完美的人，如果有多
条路径步数一样，他会选择走字典序最小的那条。
数据保证起点和终点都是0
Solution
最短路+字典序最小，非常经典的bfs题目，值得注意的是我们bfs的时候顺序应该按照题意要求的，
分别是DLRU去做，这样最先到达终点的点一定是最短且字典序最小的。
因此只需要做一遍bfs即可。
Code
#include<bits/stdc++.h>
typedef long long ll;
const int N = 1e6 + 5;
using namespace std;
char maze[505][505];
struct node {
int x, y;
int step;
string ans;
node(int _x = 0, int _y = 0, int _step = 0, string _ans = ""): x(_x), y(_y), step(_step), ans(_ans){}
};
int n, m;
bool vis[505][505];
int dist[4][2] = {1, 0, 0, -1, 0, 1, -1, 0};
string p = "DLRU";
void bfs(int x, int y) {
queue<node> q;
q.push(node(x, y, 0, ""));
vis[x][y] = 1;
while(!q.empty()) {
node now = q.front();
q.pop();
//cout << now.x << ' ' << now.y << "\n";
if(now.x == n && now.y == m) {
cout << now.step << "\n";
cout << now.ans << "\n";
return ;
}
for(int i = 0; i < 4; i++) {
int xx = now.x + dist[i][0];
int yy = now.y + dist[i][1];
//cout << xx << ' ' << yy << "\n";
if(!vis[xx][yy] && maze[xx][yy] == '0' && xx <= n && xx >= 1 && yy >= 1 && yy <= m) {
vis[xx][yy] = 1;
q.push(node(xx, yy, now.step + 1, now.ans + p[i]));
}
}
}
cout << -1 << "\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) cin >> maze[i][j];
}
bfs(1, 1);
return 0;
} 
投递XMind等公司10个岗位 >
美团成长空间 1703人发布