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

Recent Posts

Archive

Tags