April 17, 2020
LeetCode 1391: Check if There is a Valid Path in a Grid

Here we try to solve the valid path problem (#1391) given in leetcode.

There is matrix called grid is given as input. Its values are ranging from 1 to 6. Each of these numbers represent starting and eding directions of the street present in that specific cell of the grid.

  • 1 which means a street connecting the left cell and the right cell.
  • 2 which means a street connecting the upper cell and the lower cell.
  • 3 which means a street connecting the left cell and the lower cell.
  • 4 which means a street connecting the right cell and the lower cell.
  • 5 which means a street connecting the left cell and the upper cell.
  • 6 which means a street connecting the right cell and the upper cell.

We've to start from the first cell that is (0,0) and findout whether we can reach the bottom right cell (m-1,n-1) following the streets.

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        streets = {
            1: [(0, -1), (0, 1)],
            2: [(-1, 0), (1, 0)],
            3: [(0, -1), (1, 0)],
            4: [(0, 1), (1, 0)],
            5: [(0, -1), (-1, 0)],
            6: [(0, 1), (-1, 0)]
        }

        m = len(grid)
        n = len(grid[0])

        # if there is only once cell in the grid then return True
        if (m == 1 and n == 1):
            return True

        # Get next cell path values for the first street value
        paths = streets[grid[0][0]]

        # Trace the both directions of the street to find whether 
        # it can take us to the last cell
        for path in paths:
            # (i,j) represents the current cell
            i, j = 0, 0
            while (i < m and j < n):
                previous_cell = (i, j)
                # Go to the next cell by tracing the street in 
                # the direction of path values
                i, j = i + path[0], j + path[1]
                if (i >= m or j >= n or i < 0 or j < 0):
                    # if we reach a cell which is not present in the grid
                    break
                else:
                    # If the shifted cell is a valid cell in grid
                    paths = streets[grid[i][j]]

                    # find the direction in which we've reached current cell
                    # and proceed with tracing in other direction
                    if ((i + paths[0][0], j + paths[0][1]) == previous_cell):
                        path = paths[1]
                        if (i == m - 1 and j == n - 1):
                            return True
                    elif ((i + paths[1][0], j + paths[1][1]) == previous_cell):
                        path = paths[0]
                        if (i == m - 1 and j == n - 1):
                            return True
                    else:
                        return False

        return False

 

 

Credits: LeetCode