87 lines
2.9 KiB
Markdown
87 lines
2.9 KiB
Markdown
# 8.2. Robot in a Grid
|
|
|
|
> Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
|
|
|
|
Start going down, if you find some cell that can't be stepped on, go one right and down again. And so on.
|
|
|
|
```python
|
|
def go_bottom_down(r: int, c: int):
|
|
pos = [0, 0]
|
|
while pos[0] < r and pos[1] < c:
|
|
pos[0] += 1
|
|
step = can_step(pos)
|
|
while not step:
|
|
pos[1] += 1
|
|
step = can_step(pos)
|
|
```
|
|
|
|
## Hints
|
|
|
|
> For the robot to reach the last cell, it must find a path to the second-to-last cells. For it to find a path to the second-to-last cells, it must find a path to the tird-to-last cells.
|
|
|
|
I'm missing something.
|
|
|
|
> Simplify this problem by first figuring out if there's a path. Then, modify your algorithm to track the path.
|
|
|
|
But if there's no path to going down, I can go one right and try again. Why check if there's a path and then track it?
|
|
|
|
## Solution
|
|
|
|
To reach the point (r, c) we have to reach either (r-1, c) or (r, c-1). To reach (r-1, c), we can either reach (r-2, c) or (r-1, c-1). This memoization could be improved by storing the grid in memory, and whether it can be accessed or not.
|
|
|
|
You create a maze with True or False for the positions that can be stepped on.
|
|
|
|
```python
|
|
def get_path(maze):
|
|
if not maze or len(maze) == 0:
|
|
return None
|
|
|
|
path = []
|
|
if is_path(maze, len(maze)-1, len(maze[0])-1, path):
|
|
return path
|
|
return None
|
|
|
|
def is_path(maze, row, col, path):
|
|
# if out of bounds or not available, return
|
|
if col < 0 or row < 0 or not maze[row][col]:
|
|
return False
|
|
|
|
isAtOrigin = (row == 0) and (col == 0)
|
|
|
|
#if there's a path from the start to here, add my location
|
|
if isAtOrigin or isPath(maze, row, col-1, path) or isPath(maze, row-1, col,path):
|
|
path.append((row, col))
|
|
return True
|
|
return False
|
|
|
|
print(getPath([[True, True],[True,True]]))
|
|
```
|
|
|
|
This works, but many many locations are visited twice. Using memoization:
|
|
|
|
```python
|
|
def get_path_memoized(maze):
|
|
if maze == None or len(maze) == 0:
|
|
return None
|
|
|
|
path = []
|
|
visited_points = []
|
|
if is_path_memoized(maze, len(maze) - 1, len(maze[0]) - 1, path, visited_points):
|
|
return path
|
|
return None
|
|
|
|
def is_path_memoized(maze, row, col, path, visited_points):
|
|
if row < 0 or col < 0 or not maze[row][col] or (row, col) in visited_points:
|
|
return False
|
|
|
|
is_at_origin = row == 0 && col == 0
|
|
|
|
if is_at_origin or is_path_memoized(maze, row-1, col, path) or is_path_memoized(maze, row, col-1, path):
|
|
path.append((row, col))
|
|
return True
|
|
visited_points.append((row, col))
|
|
return False
|
|
|
|
print(get_path_memoized([[True,True], [False,True]]))
|
|
|
|
``` |