April 17, 2020 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)

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

# 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, j + path
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, j + paths) == previous_cell):
path = paths
if (i == m - 1 and j == n - 1):
return True
elif ((i + paths, j + paths) == previous_cell):
path = paths
if (i == m - 1 and j == n - 1):
return True
else:
return False

return False
``````

Credits: LeetCode

Recent Posts
Categories
Archive
Tags