Problem

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).

Input / Output

• Input:
  • 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 1
• Output: list[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.

Examples

Example 1

• Input: grid = [[0,0,0],[0,0,0],[0,0,0]], path = [(0,0),(0,1),(0,2),(1,2),(2,2)]
• Output: [(0,0),(2,2)]
• Explanation: (0,0)->(2,2) is clear, so all intermediate points can be removed.

Example 2

• Input: 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)]
• Output: [(0,0),(2,0),(0,2)]
• Explanation: The obstacle column blocks some shortcuts, but these two segments are clear.

Constraints

• 1 <= rows, cols <= 200
• 2 <= len(path) <= 5000
• grid[r][c] in {0,1}
• All path coordinates are in-bounds and on free cells
• Consecutive points in path are 4-neighbors