我得到了一个方形网格
0 0 0 0 0 0
1 0 0 1 1 1
1 1 0 0 0 0
1 1 1 1 1 0
1 1 1 1 0 0
1 1 1 1 1 0
我只能通过向上、向下、向左、向右移动而不能对角移动来遍历网格。我需要找到长度最多为10个单位的路径的最大y坐标。y坐标随着我们垂直向下移动而增加。
在这个例子中，它应该是6，因为我们可以到达网格的右下角。
- 我还需要知道去那里的路
- 如果有多个路径是最优的，我可以打印其中的任何一个
- 我也可以在最上面一行的任意位置开始和结束(在本例中为
0 0 0 0 0 0( - 我不能在包含1的正方形上，我只能在包含0的正方形上
我已经把这个网格读入了一个2d列表。我试图用一个修改过的dfs来解决这个问题，然而，它永远循环，没有给出答案。
def dfa(curr_X,curry,steps_taken,a,distance_from_start,path_taken=[0]):
if(not path_taken):
path_taken=[0]
if steps_taken>28:
return path_taken
else:
if a[curry+1][curr_X]!=1:
if(not path_taken):
path_taken=[0]
path_taken[0]=path_taken[0]+1
path_taken.append("01")
return dfa(curr_X,curry+1,steps_taken+1,a,distance_from_start+1,path_taken)
else:
if a[curry][curr_X+1]!=1 and a[curry][curr_X-1]!=1:
if(not path_taken):
path_taken=[0]
path_taken_right=path_taken.append("11")
path_taken_left=path_taken.append("10")
if(not path_taken):
path_taken=[0]
right_path=dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken_right)
if(not path_taken):
path_taken=[0]
left_path=dfa(curr_X-1,curry,steps_taken+1,a,distance_from_start,path_taken_left)
temp_max=max(right_path[0],left_path[0])
if(temp_max==right_path[0]):
return dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken_right)
else:
return dfa(curr_X-1,curry,steps_taken+1,a,distance_from_start,path_taken_left)
elif a[curry][curr_X+1]!=1:
path_taken.append("11")
return dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken)
elif a[curry][curr_X-1]!=1:
path_taken.append("10")
return dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken)
else:
path_taken.append("00")
path_taken[0]=path_taken[0]-1
return dfa(curr_X,curry-1,steps_taken+1,a,distance_from_start-1,path_taken)
else:
path_taken.append("00")
path_taken[0]=path_taken[0]-1
return dfa(curr_X,curry-1,steps_taken+1,airspace,distance_from_start-1,path_taken)
使用调试器逐步执行程序并不能给我一个明确的答案，说明为什么它会永远循环。很抱歉代码太长，我不能缩短它，因为我需要涵盖最佳路径从左下角或右下角开始的边缘情况。我确信这个问题需要一些dfs，然而，如果它不需要dfs，我愿意看到更好的方法。
BFS也是一种选择。
正如其他人所建议的，BFS的任何一个DFS都将解决您的问题。状态显然是网格中的位置，我们将使用Crack代码(右=0，下=1，左=2，上=3(跟踪所走的路径，这是一种基本的链代码。给定您的网格，从(0,0(位置开始：
start_coord = (0,0)
grid = [[0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[1, 1, 1, 1, 1, 0]]
由于我们希望尽快到达网格的远端，我将实现DFS，这意味着我将从右侧附加到deque，并从右侧弹出。
import collections
def find_path(grid, start_coord):
state_queue = collections.deque([]) # Pending states which have not been explored yet
visited = {start_coord}
state = [start_coord, []] # Starting state
# Keeping track of the max y reached and the path taken to get there
max_y_reached = start_coord[0] # coordinates are (y,x)
path = []
while max_y_reached < len(grid) - 1:
# Getting all possible neighboring states
state_right = [(state[0][0],state[0][1]+1), state[1] + [0]] if state[0][1]+1 < len(grid[state[0][0]]) else None
state_down = [(state[0][0]+1,state[0][1]), state[1] + [1]] if state[0][0]+1 < len(grid) else None
state_left = [(state[0][0],state[0][1]-1), state[1] + [2]] if state[0][1]-1 >= 0 else None
state_up = [(state[0][0]-1,state[0][1]), state[1] + [3]] 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
for next_state in [state_right, state_down, state_left, state_up]:
if next_state is not None:
if next_state[0] in visited or grid[next_state[0][0]][next_state[0][1]] == 1:
pass
else:
state_queue.append(next_state)
visited.add(next_state[0])
# popping next state from the queue and updating the path if needed
try:
state = state_queue.pop()
if state[0][0] > max_y_reached:
max_y_reached = state[0][0]
path = state[1]
except IndexError:
break
return max_y_reached, path
最后，当调用您得到的函数时：
max_y_reached, path = find_path(grid, start_coord)
print(max_y_reached) # 5
print(path) # [0, 1, 0, 1, 0, 0, 0, 1, 1, 1]
请注意，如果通过某个路径到达最后一行(可能的最大y坐标(，while循环将在在中间中断。如果最后一行不可访问，则DFS将在突破while循环之前检查所有可能的状态