在网格中找到路径的最大 y 坐标

Question

给我一个方格

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 的方格。

我已将此网格读入二维列表。我试图用修改后的 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 也可以是一个选项。

Answer 1

正如其他人所建议的，无论是 DFS 还是 BFS 都可以解决您的问题。状态显然是网格中的位置，我们将使用 Crack 代码（右=0，下=1，左=2，上=3）跟踪路径，这是 chain code 的基本类型.给定你的网格，从 (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]]

因为我们想尽快到达网格的 far-ends 我将实现 DFS，这意味着我将从右侧附加到双端队列并从右侧弹出。

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 循环之前遍历所有可能的状态

在网格中找到路径的最大 y 坐标

Find maximum y-coordinate of path in grid

python

algorithm