# 迷宫问题，需要用递归

<p>问题描述&#xff1a;一只老鼠在一个n×n迷宫的入口处&#xff0c;它想要吃迷宫出口处放着奶酪&#xff0c;问这只老鼠能否吃到奶酪&#xff1f;如果可以吃到&#xff0c;请给出一条从入口到奶酪的路径。
思考&#xff1a;解决问题之前&#xff0c;我们首先要做的就是仔细研究问题&#xff0c;找出问题的已知条件和要得到的是什么。和解数学问题、物理问题一样要先弄懂问题。那么&#xff0c;老鼠走迷宫问题的已知条件有什么呢&#xff1f;
数学模型重新定义问题&#xff1a;
问题&#xff1a;问老鼠能否吃到奶酪就是问能否找到一条从迷宫入口到出口的路径。如果不能找到&#xff0c;那么老鼠就吃不到奶酪&#xff1b;如果能够找到&#xff0c;那么就给出这条路径。
观察10×10的迷宫。这个迷宫其实是由10×10&#61;100个格子组成的&#xff0c;其中绿色格子代表墙&#xff0c;白色格子代表路&#xff0c;如图&#xff08;1&#xff09;所示。“绿色格子代表墙&#xff0c;白色格子代表路”是用语言形式描述的&#xff0c;需要转换成数学的形式。用1和0分别定义绿色格子和白色格子&#xff0c;可以得到如图&#xff08;2&#xff09;的迷宫。
将上面10×10的迷宫定义为如下的二维数组&#xff0c;即
         m[10][10]&#61;[1,1,1,0,1,1,1,1,1,1,
                    1,0,0,0,0,0,0,0,1,1,
                    1,0,1,1,1,1,1,0,0,1,
                    1,0,1,0,0,0,0,1,0,1,
                    1,0,1,0,1,1,0,0,0,1,
                    1,0,0,1,1,0,1,0,1,1,
                    1,1,1,1,0,0,0,0,1,1,
                    1,0,0,0,0,1,1,1,0,0,
                    1,0,1,1,0,0,0,0,0,1,
                    1,1,1,1,1,1,1,1,1,1]
有了对迷宫的数学定义&#xff0c;就可以很简单的定义迷宫的入口和出口了。迷宫的入口是m[0][3]&#xff0c;出口是m[7][9]。老鼠走迷宫问题就是要找一条从入口到出口的路径&#xff0c;如果存在就返回这条路径&#xff1b;如果不存在&#xff0c;就返回不存在这种路径。也就是说&#xff0c;要在二维数组m中找一条从m[0][3]到m[7][9]全部为0的路径。
请使用递归解决迷宫路径查找问题。
  
</p>

以下程序实现了这一功能，请你填补空白处内容：

```python
def maze(m, n, route, pos, export):
	"""走迷宫
	m	   - 迷宫数组，列表
	n	   - 迷宫阶数
	route   - 可能的路线，列表
	pos	 - 当前位置，元组
	export  - 出口位置，元组
	"""
	route.append(pos)
	if pos == export:
		print(route)
	if pos[0] > 0 and m[pos[0]-1][pos[1]] == 0 and (pos[0]-1,pos[1]) not in route:
		maze(m, n, route[:], (pos[0]-1,pos[1]), export)
	if pos[0] < n-1 and m[pos[0]+1][pos[1]] == 0 and (pos[0]+1,pos[1]) not in route:
		maze(m, n, route[:], (pos[0]+1,pos[1]), export)
	if pos[1] > 0 and m[pos[0]][pos[1]-1] == 0 and (pos[0],pos[1]-1) not in route:
		maze(m, n, route[:], (pos[0],pos[1]-1), export)
	________________________________;
m = [
	[1,1,1,0,1,1,1,1,1,1], 
	[1,0,0,0,0,0,0,0,1,1], 
	[1,0,1,1,1,1,1,0,0,1], 
	[1,0,1,0,0,0,0,1,0,1], 
	[1,0,1,0,1,1,0,0,0,1], 
	[1,0,0,1,1,0,1,0,1,1], 
	[1,1,1,1,0,0,0,0,1,1], 
	[1,0,0,0,0,1,1,1,0,0], 
	[1,0,1,1,0,0,0,0,0,1], 
	[1,1,1,1,1,1,1,1,1,1] 
]
maze(m, len(m), list(), (0,3), (7,9))
```

## template

```python
def maze(m, n, route, pos, export):
	"""走迷宫
	m	   - 迷宫数组，列表
	n	   - 迷宫阶数
	route   - 可能的路线，列表
	pos	 - 当前位置，元组
	export  - 出口位置，元组
	"""
	route.append(pos)
	if pos == export:
		print(route)
	if pos[0] > 0 and m[pos[0]-1][pos[1]] == 0 and (pos[0]-1,pos[1]) not in route:
		maze(m, n, route[:], (pos[0]-1,pos[1]), export)
	if pos[0] < n-1 and m[pos[0]+1][pos[1]] == 0 and (pos[0]+1,pos[1]) not in route:
		maze(m, n, route[:], (pos[0]+1,pos[1]), export)
	if pos[1] > 0 and m[pos[0]][pos[1]-1] == 0 and (pos[0],pos[1]-1) not in route:
		maze(m, n, route[:], (pos[0],pos[1]-1), export)
	if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route:
		maze(m, n, route[:], (pos[0],pos[1]+1), export)
m = [
	[1,1,1,0,1,1,1,1,1,1], 
	[1,0,0,0,0,0,0,0,1,1], 
	[1,0,1,1,1,1,1,0,0,1], 
	[1,0,1,0,0,0,0,1,0,1], 
	[1,0,1,0,1,1,0,0,0,1], 
	[1,0,0,1,1,0,1,0,1,1], 
	[1,1,1,1,0,0,0,0,1,1], 
	[1,0,0,0,0,1,1,1,0,0], 
	[1,0,1,1,0,0,0,0,0,1], 
	[1,1,1,1,1,1,1,1,1,1] 
]
maze(m, len(m), list(), (0,3), (7,9))
```

## 答案

```python
if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route:
	maze(m, n, route[:], (pos[0],pos[1]+1), export)
```

## 选项

### A

```python
if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route:
	maze(m, n, route[:], (pos[0],pos[1]), export)
```

### B

```python
if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route:
	maze(m, n, route[:], (pos[0],pos[1]-1), export)
```

### C

```python
if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route:
	maze(m, n, route[:], (pos[0],pos[0]+1), export)
```