At RoboNav, you are given a valid 4-neighbor grid path and want to remove as many intermediate waypoints as possible by replacing subpaths with straight segments that have clear line-of-sight.
A segment between two cells a and b is allowed if every grid cell touched by the segment is free (0). Use Bresenham’s line algorithm to enumerate the touched cells (inclusive).
grid: list[list[int]] where grid[r][c] is 0 (free) or 1 (blocked)path: list[tuple[int,int]] where each consecutive pair is Manhattan distance 1list[tuple[int,int]] which is a subsequence of path (keep order) with the minimum number of waypoints.If multiple minimum-waypoint answers exist, choose the one with the lexicographically smallest sequence of indices from the original path.
Example 1
grid = [[0,0,0],[0,0,0],[0,0,0]], path = [(0,0),(0,1),(0,2),(1,2),(2,2)][(0,0),(2,2)](0,0)->(2,2) is clear, so all intermediate points can be removed.Example 2
grid = [[0,1,0],[0,1,0],[0,0,0]], path = [(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2)][(0,0),(2,0),(0,2)]1 <= rows, cols <= 2002 <= len(path) <= 5000grid[r][c] in {0,1}path coordinates are in-bounds and on free cellspath are 4-neighbors