要获取所有路径，可以使用 DFS 或 BFS，但每个路径需要有唯一的visited设置为跟踪您：
- 不要在一条路径中两次返回同一坐标
- 允许不同的路径走在同一坐标上
我为网格编写了 DFS 实现here解决方案将依赖于这个例子。
Solution
要进行图搜索，需要定义状态，在本例中是坐标，但对于这个问题，为了方便起见，我们将跟踪两个参数：
- 所采取的路径将通过破解代码（right = 0，down = 1，left = 2，up = 3）记录，这是一种形式链码
- the
visited由于上述原因，为每个路径设置的内容将被取消记录
Python中的实现如下（在我的例子中，左上角匹配坐标（0,0），右下角匹配坐标（n-1,n-1）nXn grid)
import collections
def find_paths(grid, start_coord):
paths = set() # paths will be added here
state_queue = collections.deque([]) # Pending states which have not been explored yet
# State is a tuple consists of:
# 1. current coordinate
# 2. crack code path
# 3. set of visited coordinates in that path
state = [start_coord, [], {start_coord}] # Starting state
while True:
# Getting all possible neighboring states
# Crack code (right=0, down=1, left=2, up=3)
state_right = [(state[0][0],state[0][1]+1), state[1] + [0], state[2].copy()] if state[0][1]+1 < len(grid[state[0][0]]) else None
state_down = [(state[0][0]+1,state[0][1]), state[1] + [1], state[2].copy()] if state[0][0]+1 < len(grid) else None
state_left = [(state[0][0],state[0][1]-1), state[1] + [2], state[2].copy()] if state[0][1]-1 >= 0 else None
state_up = [(state[0][0]-1,state[0][1]), state[1] + [3], state[2].copy()] if state[0][0]-1 >= 0 else None
# Adding to the queue all the unvisited states, as well as to the visited to avoid returning to states
blocked_counter = 0
for next_state in [state_right, state_down, state_left, state_up]:
if next_state is None:
blocked_counter += 1
elif next_state[0] in state[2] or grid[next_state[0][0]][next_state[0][1]] == 0:
blocked_counter += 1
else:
next_state[2].add(next_state[0])
state_queue.append(next_state)
# After checking all directions' if reached a 'dead end', adding this path to the path set
if blocked_counter == 4:
paths.add(tuple(state[1]))
# Popping next state from the queue and updating the path if needed
try:
state = state_queue.pop()
except IndexError:
break
return paths
解释
-
首先，我们创建初始状态，以及初始路径（空列表）和visited设置，仅包含起始坐标
-
对于我们所处的每个状态，我们都会执行以下操作：
2.1.创建四个相邻状态（向右、向上、向左或向下前进）
2.2.通过检查我们所在的路径是否已经访问过该坐标以及该坐标是否有效来检查我们是否可以在每个方向上前进
2.3.如果我们可以朝上述方向前进，请添加此next_state to the state_queue以及visited路径的集合
2.4.如果我们不能在四个方向中的任何一个方向前进，我们就到达了“死胡同”，我们将我们所在的路径添加到paths set
2.5.弹出下一个状态state_queue这是一个不好的名字，因为它是一个堆栈（由于从堆栈的同一侧追加和弹出）deque()
-
当。。。的时候state_queue为空，我们完成了搜索，我们可以返回所有找到的路径
当使用给定的示例运行时，即
start_coord = (1,1)
grid = [[1, 1, 1],
[1, 1, 0],
[1, 1, 1]]
We get:
find_paths(grid, start_coord)
# {(2, 3, 0, 0), (3, 2, 1, 1, 0, 0), (3, 0), (2, 1, 0, 0), (1, 0), (1, 2, 3, 3, 0, 0)}
