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 ```python 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.