列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1691
经　　验	2704
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)
浏览：273

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)
浏览：2108

蓝桥杯算法提高- 拿糖果动态规划 (C++)
浏览：444

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

蓝桥杯算法提高-学霸的迷宫 BFS- (C++)

　　作者: 列公子　　　　发表时间：2020-02-13 23:30:52 浏览：635　|　评论：1　

原题链接：蓝桥杯算法提高VIP-学霸的迷宫

# 1923题-[蓝桥杯][算法提高]学霸的迷宫 [BFS] (C++)

## 1. 问题转化

求给定起点和终点的最短路径, 可以由一次 **BFS** 得到**最短距离**和**路径信息**

## 2. 算法

借助队列迭代的广度优先搜索

## 3. 数据结构

队列中的元素为结构体 ```Node``` 的实例
```cpp
struct Node{
	int x, y, layer;	// 当前节点坐标, 已经走了多少步(递归层次)
	string path;		// 已经走过的路径的各个方向
}
```
先前考虑有一个这样的结构, 保存节点的**前驱节点信息**

```cpp
struct Node{
	int x, y;		// 前驱节点坐标
	char direction;		// 该节点相对于前驱节点的方位
}

Node pre[maxn][maxn];
```
然后借助一个这样的递归回溯算法, 打印出所有的方向。
```cpp
void backtrack(int x, int y){
	if (x == 0 && y == 0)
		return;
	backtrack(pre[x][y].x, pre[x][y].y);
	printf("%d", pre[x][y].direction);
}
```
这样无法保证字典序, 因此将路径保存在队列的 ```Node```节点中, 在 ```BFS```遍历当前节点的四个邻接节点时, 按照字典序遍历。

## 4. 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 算法提高 1923 学霸的迷宫
#include <cstdio>
#include <iostream>
#include <queue>
#include <map>
using namespace std;
const int maxn = 510;

char maze[maxn][maxn];  // 迷宫
bool vis[maxn][maxn];   // 是否入队
int N, M;

struct Node{
    int x, y, layer;
    string path;
    Node(int xx, int yy, int ll, string pp){
        x = xx, y = yy, layer = ll;
        path = pp;
    }
    Node(){}
};

int direction[4][2] = {
        {1, 0},     // 下
        {0, -1},    // 左
        {0, 1},      // 右
        {-1, 0}     // 上
};
char location[4] = {'D', 'L', 'R', 'U'};

void bfs(int x, int y){
    queue<Node> q;
    q.push(Node(x, y, 0, ""));
    vis[x][y] = true;

while (!q.empty()){
        Node cur = q.front();
        q.pop();

if (cur.x == N - 1 && cur.y == M - 1){
            cout << cur.layer << endl << cur.path;
            return;
        }

for (int i = 0; i < 4; i++){
            int tx = cur.x + direction[i][0];
            int ty = cur.y + direction[i][1];

if (tx > -1 && tx < N && ty > -1 && ty < M && !vis[tx][ty] && maze[tx][ty] == '0'){
                Node newNode = Node(tx, ty, cur.layer + 1, cur.path + location[i]);
                q.push(newNode);
                vis[tx][ty] = true;
            }
        }
    }
}

int main(){
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; i++)
        cin >> maze[i];
    bfs(0, 0);
    return 0;
}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

青白

为什么变成下 右 左 上类似这样的顺序就错了呀

2024-03-18 16:08:57

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C二级辅导-求偶数和（C语言代码）

C二级辅导-统计字符（C语言代码）

宏定义

蓝桥杯算法提高-学霸的迷宫 BFS- (C++)

评论区

精彩推荐

采药（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

大神老白（C语言代码）

时间转换（Java代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

兰顿蚂蚁（C++代码）

回文串（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C二级辅导-统计字符 （C语言代码）

宏定义

蓝桥杯算法提高-学霸的迷宫 BFS- (C++)

评论区

精彩推荐

采药 （C++代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

大神老白 （C语言代码）

时间转换 （Java代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

兰顿蚂蚁 （C++代码）

回文串 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C二级辅导-求偶数和（C语言代码）

C二级辅导-统计字符（C语言代码）

　　评论区

采药（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

大神老白（C语言代码）

时间转换（Java代码）

兰顿蚂蚁（C++代码）

回文串（C语言代码）