Geodesic Distance on a Grid
Implement geodesic_distance(grid, goal), where grid is a 2D array of 0 (open) and 1 (wall) and goal is [row, col]. Return an integer array the same shape as grid, with −1 for walls and unreachable cells.
Examples
An open corridor: distance is just how many cells back you are
- Input
- geodesic_distance([[0, 0, 0]], [0, 2])
- Output
- [[2, 1, 0]]
A pillar in the middle: the corner is 4 moves away, not 2.83
- Input
- geodesic_distance([[0, 0, 0], [0, 1, 0], [0, 0, 0]], [0, 0])
- Output
- [[0, 1, 2], [1, -1, 3], [2, 3, 4]]
A wall can seal a cell off entirely
- Input
- geodesic_distance([[0, 1, 0]], [0, 0])
- Output
- [[0, -1, -1]]
Hints
Hint 1
Build the result up as you go, then return it.
Hint 2
Watch for this: used straight line distance which measures through walls.
Requirements
grid: (H, W) array, 0 = open, 1 = wallgoal: [row, col] of the target cell
Constraints
Allowed library: NumPy only
Time limit: 200 ms, Memory: 64 MB
Try similar problems(4)
Reinforcement Learning: Rewards, Senses and PPO · ~18 min
Reinforcement Learning: Rewards, Senses and PPO · ~16 min
Reinforcement Learning: Rewards, Senses and PPO · ~20 min
Reinforcement Learning: Rewards, Senses and PPO · ~14 min
import numpy as np
from collections import deque
def geodesic_distance(grid, goal):
"""
Shortest number of 4-connected moves from every open cell to the goal.
Args:
grid: (H, W) array, 0 = open, 1 = wall
goal: [row, col] of the target cell
Returns:
(H, W) integer array of move counts, -1 for walls and for open
cells the goal cannot reach.
"""
# YOUR CODE HERE
pass