牛牛走迷宫（bfs最短路）

题目链接
思路：从题意走的步数最小可以知道这道题肯定是求最短路（一般我用bfs），但字典序最小卡住了我，其实要求字典序最小其实我们只需要把每步走的四个方向所代表的字符按字典序最小排列即可，即“DLRU”(先向下，再向左，再向右，最后向上)，那么bfs时字典序最小的路径总会在字典序的路径之前，这样所求的最短路便是符合要求的最短路。
ac代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
using namespace std;
#define int long long
string lll = "DLRU";
int dis[4][2] = { {1,0},{0,-1},{0,1},{-1,0} }; int n, m;
char cnt[505][505];
int vis[505][505];
struct node {
int x, y;
string path;
node(int _x, int _y, string _path) :x(_x), y(_y), path(_path) {}
};
void bfs(int a, int b) {
queue<node> k;
k.push(node(0, 0, ""));
vis[0][0] = 1;
while (!k.empty()) {
node mm = k.front(); k.pop();
for (int i = 0; i < 4; i++) {
int c = mm.x + dis[i][0];
int d = mm.y + dis[i][1];
if (c >= 0 && c < n && d >= 0 && d < m && !vis[c][d] && cnt[c][d] == '0') {
vis[c][d] = 1;
if (c == n - 1 && d == m - 1) {
string ccc = mm.path;
cout << ccc.size()+1 << endl << ccc + lll[i] << endl;
return;
}
string cc = mm.path + lll[i];
k.push(node(c, d, cc));
}
}
}
cout << -1 << endl;
return ;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> cnt[i][j];
bfs(n, m);
return 0;
}

最后

以上就是调皮机器猫为你收集整理的牛牛走迷宫（bfs最短路）的全部内容，希望文章能够帮你解决牛牛走迷宫（bfs最短路）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。