迷宫寻路

缘起

邓俊辉的数据结构和算法(C++语言版) 第四章的例子

需求是我要救老婆. 老婆在迷宫的某处. 而这个迷宫有一些障碍物, 我不能越过. 找出最短的救老婆的路径.

分析

其实这题既可以用dfs，也可以使用bfs. 使用dfs本质就是递归, 和八皇后那题一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <stack>
#define LOCAL

using namespace std;

// w*h 是棋盘的尺寸, targetX和targetY是目标横纵坐标
int w,h,targetX,targetY,minSteps = 99999999;
// board 是棋盘, book 是标志棋盘有没有被占用, book[][]=0 表示没有被占用, 1表示被占用了
int board[55][55], book[55][55];
int nxt[4][2] = {
	1,0,
	-1,0,
	0,1,
	0,-1
};

// 一步的结构体
struct Step {
	int x, y;
	Step* prev;
}*solu;

// 判断下一步是否可以
bool isok(Step& next) {
	// 不越界、不是障碍物、并且没有被占据（因为被占据相当于走回去了，这显然不是最优解，完全可以剪枝掉）
	return next.x>=1&&next.x<=w&&next.y>=1&&next.y<=h &&!board[next.x][next.y]&&!book[next.x][next.y];
}

// step 是当前的位置, steps 是目前走的步数 注意, 这里的入参必须要是Step 而不能写成是 Step & 不然的话, 就只有一块Step内存了,
void dfs(Step current, int steps)
{
	// 到达目标
	if (current.x == targetX && current.y == targetY)
	{
		// 如果代价更小的话
		if (minSteps > steps)
		{
			// 更新
			minSteps = steps;
			// 顺藤摸瓜就能回去
			solu = &current;
			// 注意, 为什么不能得到了最优的solu之后再打印最优的路径，而是找到一条打印一条, 这是因为返回上一层的时候, 本层栈帧就会被销毁, 本层的Step 就不在了.就会变成大的夸张的数字, 所以只能找到一条打印一条
			cout<< "找到一条路径如下"<<endl;
			stack<Step> steps;
			while(solu->prev){
				steps.push(*solu);
				solu = solu->prev;
			}
			while(!steps.empty()) {
				Step s = steps.top();
				printf("(%d, %d)", s.x, s.y);
				steps.pop();
			}
		}
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		Step next = {current.x+nxt[i][0], current.y+nxt[i][1], &current};
		// 如果没有被占用并且棋盘上不是障碍物的话
		if (isok(next))
		{
			// 锁上
			book[next.x][next.y] = 1;
			dfs(next, steps+1);
			// 解锁
			book[next.x][next.y] = 0;
		}
	}
}

// 负责输入
void input()
{
    // 测试数据可以参见 啊哈算法第三章
	printf("请输入棋盘的宽度和高度:\n");
	scanf("%d", &w);
	scanf("%d", &h);
	for (int i = 1; i<= w;i++)
	{
		for (int j = 1; j<=h;j++)
		{
			scanf("%d", &board[i][j]);
		}
	}
	printf("请输入目标:\n");
	scanf("%d %d", &targetX, &targetY);
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	input();
	Step start = {1,1,NULL};
	// 起点已经被占据了
	book[start.x][start.y] = 1;
	dfs(start, 0);
	cout<<"最小步数是: "<<minSteps<<endl;
	
	return 0;
}

ps: 本题完全可以类似于八皇后那题，翻译成栈版本. 思想是一样的.