# 回溯算法-迷宫问题

给定一个迷宫，入口已知，确定是否有路径从入口到出口，有则输出。可以8个方向移动

```python
maze=[[1,1,1,1,1,1,1,1,1,1],
      [0,0,1,0,1,1,1,1,0,1],
      [1,1,0,1,0,1,1,0,1,1],
      [1,0,1,1,1,0,0,1,1,1],
      [1,1,1,0,0,1,1,0,1,1],
      [1,1,0,1,1,1,1,1,0,1],
      [1,0,1,0,0,1,1,1,1,0],
      [1,1,1,1,1,0,1,1,1,1]
]

m,n=8,10 #8行，10列
entry=(1,0) #入口 
path=[entry]
paths=[] #一组解
directions=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def confliction(nx,ny):
    # 是否冲突
    global m,n,maze
    if 0<=nx<m and 0<=ny<n and maze[nx][ny]==0:
        return False
    return  True
def walk(x,y):
    global entry,m,n,maze,path,paths,directions

    if (x,y)!=entry and ((x%(m-1))==0 or (y%(n-1))==0):#到最外边，则添加为一条完整路径
        paths.append(path[:])
    else:
        for d in directions:#遍历所有方向
            nx,ny=x+d[0],y+d[1]
            path.append((nx,ny))
            if not confliction(nx,ny):#如果不冲去，就当前点为起点，继续下一步
                maze[nx][ny]=2 #标记为访问
                walk(nx,ny)
                maze[nx][ny]=0 #回溯，恢复不标记状态，以被后续使用
            path.pop()#回溯

def show(path):
    import pprint,copy
    maze2=copy.deepcopy(maze)
    for p in path:
        maze2[p[0]][p[1]]=2
    pprint.pprint(maze)
    print()
    pprint.pprint(maze2)


walk(1,0)
# print(paths)
print(paths[-1],'\n')
show(paths[-1])
```

```
[(1, 0), (1, 1), (2, 2), (1, 3), (2, 4), (3, 5), (4, 4), (4, 3), (5, 2), (6, 3), (6, 4), (7, 5)] 

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 0, 1, 0, 1, 1, 1, 1, 0, 1],
 [1, 1, 0, 1, 0, 1, 1, 0, 1, 1],
 [1, 0, 1, 1, 1, 0, 0, 1, 1, 1],
 [1, 1, 1, 0, 0, 1, 1, 0, 1, 1],
 [1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
 [1, 0, 1, 0, 0, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 0, 1, 1, 1, 1]]

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 1, 2, 1, 1, 1, 1, 0, 1],
 [1, 1, 2, 1, 2, 1, 1, 0, 1, 1],
 [1, 0, 1, 1, 1, 2, 0, 1, 1, 1],
 [1, 1, 1, 2, 2, 1, 1, 0, 1, 1],
 [1, 1, 2, 1, 1, 1, 1, 1, 0, 1],
 [1, 0, 1, 2, 2, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 2, 1, 1, 1, 1]]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/si-xiang-lei/hui-su/mi-gong-wen-ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.