深度优先搜索-迷宫问题（计蒜客-蓝桥杯国赛训练营）

2023-10-08 09:57:28

文章目录

深度优先搜索-迷宫问题

深度优先搜索-迷宫问题

视频学习链接：https://www.bilibili.com/video/BV1pk4y1z76B
深度优先搜索：简称dfs,是一个经典的搜索算法。

递归回顾

前面有学习过递归，我们使用递归实现了一些算法：

# 1.递归实现阶乘
# n! = 1*2*3*4******n
def factorial(n):
	if (n ==1 ):
		return 1
	else:
		return n *factorial(n-1)
print(factorial(10))
# 2.斐波拉契数列
# 1 1 2 3 5 8------
def fib(n):
	if (n==1||n==2):
		return 1
	else:
		return fib(n-1)+fib(n-2)

深度优先搜索实际上是一种穷举的方式，把所有可行的方案都列出来，不断去尝试，直到找到问题的解。

深度优先搜索和递归的区别是：深度优先搜索是一种算法，注重的是思想；而递归是一种基于编程语言的实现方式。深度优先搜索可以用递归实现，也就是说递归是我们用计算机编程语言来实现深度优先搜索这个算法的手段。

接下来，我们通过一个实际问题————迷宫游戏来学习dfs

迷宫游戏

我们用一个二维的字符数组来表示前面画出的迷宫：

S**
···
***T

其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符·表示平地。每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。

迷宫问题的解法就需要用到dfs.我们对上下左右四个方向，一个方向一个方向地尝试，如果沿着某个方向不能走到终点，我们就要原路返回，继续尝试其他方向，直到走出迷宫。这是一种最朴素的走迷宫方式，虽然效率也许比较低，但如果迷宫有解，就一定能走出终点。

上面说的这种走法，就对应着我们要讲的dfs算法。首先找到起点s，走到每个点时，按照左、下、右、上的顺序（逆时针）尝试。每走到下一个点以后，我们把这个点当做起点s,继续按顺序尝试。如果某个点上下左右四个方向都尝试过，便回到走到这个点之前的点，这一步我们称之为回溯。继续尝试其他方向。直到所有点都尝试过上下左右四个方向。

这就好比你自己去走这个迷宫，你也要一个方向一个方向的尝试着走，如果这条路不行，就回头，尝试下一条路，dfs 的思想和我们直观的想法很类似。只不过，接下来我们需要用程序来完成这个过程。

迷宫基础版

# 3迷宫基础版
# 行 列
n , m = [int(i) for i in input("").split()]
# 迷宫初始化
maze = []
for i in range(0,n):
	list1 = list(input(""))
	maze.append(list1)
# 对迷宫进行标记
vis = []
for i in range(0,n):
	list1 = [0]*m
	vis.append(list1)


def dfs(x,y):
	# 出迷宫则返回true
	if(maze[x][y]=="T"):
		return 1
	# 对位置进行标记
	vis[x][y] = 1
	# 显示路径
	maze[x][y] ='m'
	# 上左下右
	# 上
	tx = x - 1 
	ty = y
	if tx >= 0 and tx < n and ty >= 0 and ty < m and maze[tx][ty] != '*' and vis[tx][ty] == 0 :
		if (dfs(tx,ty)):
			return 1
	# 左
	tx = x 
	ty = y - 1
	if tx >= 0 and tx < n and ty >= 0 and ty < m and maze[tx][ty] != '*' and vis[tx][ty] == 0 :
		if (dfs(tx,ty)):
			return 1
	# 下
	tx = x + 1
	ty = y 
	if tx >= 0 and tx < n and ty >= 0 and ty < m and maze[tx][ty] != '*' and vis[tx][ty] == 0 :
		if (dfs(tx,ty)):
			return 1
	# 右
	tx = x 
	ty = y + 1
	if tx >= 0 and tx < n and ty >= 0 and ty < m and maze[tx][ty] != '*' and vis[tx][ty] == 0 :
		if (dfs(tx,ty)):
			return 1
	# 找不到的时候，取消标记
	vis[x][y] = 0
	maze[x][y] ='.'
	return 0

# 开始走迷宫
for i in range(0,n):
	for j in range(0,m):
		# 找到起始点
		if maze[i][j] == 'S':
			x = i
			y = j
# 能走通就把路径显示出来
if dfs(x,y):
	for i in range(0,n):
		print(maze[i])
# 不能走通就显示NO
else:
	print("NO!")

测试：

迷宫精简版

# 4迷宫精简版
# 行 列
n , m = [int(i) for i in input("").split()]
# 迷宫初始化
maze = []
for i in range(0,n):
	list1 = list(input(""))
	maze.append(list1)
# 对迷宫进行标记
vis = []
for i in range(0,n):
	list1 = [0]*m
	vis.append(list1)

# ---------进阶修改部分

# 将方向存为数组:上左下右
direction = [[-1,0],[0,-1],[1,0],[0,1]]

def dfs(x,y):
	# 出迷宫则返回true
	if(maze[x][y]=="T"):
		return 1
	# 对位置进行标记
	vis[x][y] = 1
	# 显示路径
	maze[x][y] ='m'

	# 上左下右
	for i in range(0,len(direction)):
		tx = x + direction[i][0]
		ty = y + direction[i][1]
		if tx >= 0 and tx < n and ty >= 0 and ty < m and maze[tx][ty] != '*' and vis[tx][ty] == 0 :
			if (dfs(tx,ty)):
				return 1

	# 找不到的时候，取消标记
	vis[x][y] = 0
	maze[x][y] ='.'
	return 0

# -------------进阶修改部分

# 开始走迷宫
for i in range(0,n):
	for j in range(0,m):
		# 找到起始点
		if maze[i][j] == 'S':
			x = i
			y = j
# 能走通就把路径显示出来
if dfs(x,y):
	for i in range(0,n):
		print(maze[i])
# 不能走通就显示NO
else:
	print("NO!")
    
# 测试结果相同

迷宫高级版

（走迷宫的路线数、路线图、最少步数）

# 5迷宫高级版
# 行 列
n , m = [int(i) for i in input("").split()]
# 迷宫初始化
maze = []
for i in range(0,n):
	list1 = list(input(""))
	maze.append(list1)
# 对迷宫进行标记
vis = []
for i in range(0,n):
	list1 = [0]*m
	vis.append(list1)

# ------------------高阶修改部分

# 将方向存为数组:上左下右
direction = [[-1,0],[0,-1],[1,0],[0,1]]
# 路线步数的存储
dirstep = []

def dfs(x,y,step):
	# 出迷宫则返回true
	if(maze[x][y]=="T"):
		# 输出路线图
		for j in range(0,n):
			print(maze[j])
		# 输出该路线的步数
		print(step)
		dirstep.append(step)
		return 1
	# 对位置进行标记
	vis[x][y] = 1
	# 显示路径
	maze[x][y] ='m'

	# 上左下右
	for i in range(0,len(direction)):
		tx = x + direction[i][0]
		ty = y + direction[i][1]
		if tx >= 0 and tx < n and ty >= 0 and ty < m and maze[tx][ty] != '*' and vis[tx][ty] == 0 :
			dfs(tx,ty,step+1)

	# 找不到的时候，取消标记
	vis[x][y] = 0
	maze[x][y] ='.'
	return 0

# 开始走迷宫
for i in range(0,n):
	for j in range(0,m):
		# 找到起始点
		if maze[i][j] == 'S':
			x = i
			y = j
# 调用函数
dfs(x,y,0)

print(dirstep)
# 最短步数
print(min(dirstep))
# 多少种走法
print(len(dirstep))

if len(dirstep) > 0:
	print("Yes")
else:
	print("NO")

# ------------------高阶修改部分

测试：

迷宫练习题

题目要求

中国象棋博大精深，其中马的规则最为复杂，也是最难操控的一颗棋子。
我们都知道象棋中马走"日”，比如在(2, 4)位置的一个马，跳一步能到达的位置有(0,3)，(0, 5)，(1,2)，(1,6)，(3,2)，(3,6)，(4,3)，(4,5)。

蒜头君正在和花椰妹下棋，蒜头君正在进行战略布局，他需要把在(x, y)位置的马跳到(x’,y’)位置，以达到威慑的目的。
但是棋盘大小有限制，棋盘是一个10 x 9的网格，左上角坐标为(0,0),右下角坐标为(9, 8),
马不能走出棋盘，并且有些地方已经有了棋子，马也不能跳到有棋子的点。
蒜头君想知道，在不移动其他棋子的情况下，能否完成他的战略目标。

输入格式
输入一共10行，每行一个长度为9的字符串。输入表示这个棋盘，我们用“.”表示空位置，
用’#‘表示该位置有棋子，用’S’表示初始的马的位置，用’T’表示马需要跳到的位置。
输入保证一定只存在一个’S’和一个"T’。

输出格式
如果在不移动其他棋子的情况下，马能从’S’跳到’T’，那么输出一行"Yes"，否则输出一
行"No" .

解题

# 建立迷宫
maze = []
for i in range(0,10):
	list1 = list(input(""))
	maze.append(list1)

# 建立迷宫标记
vis = []
for i in range(0,10):
	list1 = [0]*9
	vis.append(list1)

direction = [[-2,-1],[-1,-2],[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1]]

def dfs(x,y):
	if maze[x][y] == 'T':
		return 1
	# 进行标记
	vis[x][y] = 1
	maze[x][y] = 'm'

	# 对方向进行遍历
	for i in range(0,len(direction)):
		tx = x + direction[i][0]
		ty = y + direction[i][1]
		if tx >= 0 and tx < 10 and ty >= 0 and ty < 9 and maze[tx][ty] != '#' and vis[tx][ty] == 0:
			if dfs(tx,ty):
				return 1


	# 若没有找到，取消标记
	vis[x][y] = 0
	maze[x][y] = '.'
	return 0

# 遍历迷宫，寻找起始点
for i in range(0,10):
	for j in range(0,9):
		if maze[i][j] == 'S':
			x = i
			y = j

if dfs(x,y):
	print('YES')
	for i in range(0,10):
		print(maze[i])
else:
	print('NO')

测试：

码农公寓