Longest Straight-Line Robot Walk in a Grid with Forbidden Rows and Columns

A robot stands in a grid of rows rows and cols columns, at row start_row and column start_col. Rows are numbered from 0 at the top and columns from 0 at the left. Some entire rows and some entire columns are forbidden: entering any cell of a forbidden row or a forbidden column destroys the robot.

The robot picks exactly one of the four directions (up, down, left or right) and walks in a straight line in that direction, one cell per step, without ever turning. Return the largest number of steps the robot can walk safely.

Function Signature

def longest_straight_walk(rows: int, cols: int, start_row: int, start_col: int, blocked_rows: list[int], blocked_cols: list[int]) -> int:

Rules

• A walk in the chosen direction continues as long as the next cell is inside the grid and is in neither a forbidden row nor a forbidden column. It ends on the last safe cell: at the edge of the grid, or just before the first cell in its path that lies in a forbidden row or column.
• The number of steps is the number of cells moved, not counting the starting cell.
• The result is the maximum number of steps over the four directions. It is 0 when every direction is blocked immediately, including when the robot starts on an edge and every other direction is blocked.
• The starting cell is never in a forbidden row or a forbidden column.

Constraints

• 1 <= rows <= 10^9 and 1 <= cols <= 10^9
• 0 <= start_row < rows and 0 <= start_col < cols
• 0 <= len(blocked_rows) <= 100000 and 0 <= len(blocked_cols) <= 100000
• Every value of blocked_rows is in [0, rows - 1] and every value of blocked_cols is in [0, cols - 1]. Values within each list are distinct and may appear in any order.
• start_row is not in blocked_rows and start_col is not in blocked_cols.
• The result is at most 10^9 - 1, which fits in a signed 32-bit integer.

Examples

Example 1

• Input: rows = 4, cols = 10, start_row = 1, start_col = 2, blocked_rows = [3], blocked_cols = [0, 8]
• Output: 5
• Explanation: Up reaches row 0 in 1 step. Down reaches row 2 in 1 step and stops before forbidden row 3. Left reaches column 1 in 1 step and stops before forbidden column 0. Right reaches column 7 in 5 steps and stops before forbidden column 8. The best is 5.

Example 2

• Input: rows = 5, cols = 5, start_row = 2, start_col = 2, blocked_rows = [1, 3], blocked_cols = [1, 3]
• Output: 0
• Explanation: The first cell in every direction lies in a forbidden row or column, so the robot cannot move at all.

Example 3

• Input: rows = 9, cols = 4, start_row = 6, start_col = 1, blocked_rows = [8, 2], blocked_cols = [3]
• Output: 3
• Explanation: Up passes rows 5, 4 and 3 and stops before forbidden row 2, for 3 steps. Down reaches row 7 in 1 step. Left reaches column 0 in 1 step. Right reaches column 2 in 1 step and stops before forbidden column 3.

Longest Straight Walk Between Forbidden Lines

Hints

1. When the robot walks up or down it stays in column start_col, which is never forbidden. Which of the two lists can actually stop a vertical walk?
2. Among the forbidden rows above the start, only one of them matters for the upward walk. Which one, and how many steps does it leave?
3. The grid can have 10^9 rows, so simulating cell by cell is too slow; a single pass over each list is enough, and sorting is not required.