Find maximum y-coordinate of path in grid

Question

I am given a square 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

I can traverse the grid by only moving up, down, left, right but not diagonally. I need to find the maximum y-coordinate of the path with a length of at most 10 units. y-coordinate increases as we move downwards vertically.

In this example, it would be 6, as we can reach the bottom right of the grid.

• I also need to know the path of the way to get there.
• If there are multiple paths that are optimal, I can print any one of them.
• I can also start and end anywhere I choose on the top row(0 0 0 0 0 0 in this case)
• I cannot go on a square that contains a 1, I can only go on squares that contain a 0.

I have read this grid into a 2d list. I have attempted to solve this with a modified dfs, however, it loops forever and does not give an answer.

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)

Stepping through the program with a debugger does not give me a definitive answer as to why it loops forever. Sorry for the long code, I cannot shorten it as I need to cover edge cases where the optimal path starts at the bottom left or bottom right. I am sure that this problem requires some dfs, however, if it does not require dfs, I am open to seeing a better method.

BFS could also be a option.

Answer 1

As others have suggested, either DFS of BFS will solve your problem. The states are obviously the locations in the grid and we will keep track of the path taken using Crack code (right=0, down=1, left=2, up=3), which is a basic sort of chain code. Given your grid, starting from the (0,0) position:

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]]

Since we want to reach the far-ends of the grid as fast as possible I will implement DFS, meaning I will append to the deque from the right and pop from the right as well.

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

Finally, when calling the function you get:

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]

Note that if by some path you reached the last row (maximal y coordinate possible), the while loop will break in the middle. If the last row is not reachable, the DFS will go over all the possible states before breaking out of the while loop