Spiral Order of a Matrix With Blocker Cells That Force Clockwise Turns

You are given an m x n matrix of integers. First, return all of its values in clockwise spiral order, from the outside in: start at the top-left cell, move right along the top row, down the right column, left along the bottom row, up the left column, and continue inward.

Follow-up: the matrix may contain blockers. The traversal never enters a blocker; when it runs into one, it turns clockwise (a right turn), the same way it turns at the matrix edge or at a cell it has already visited. Return the values in the order they are visited. Without blockers the result is the ordinary spiral order, so a single function covers both questions.

The report leaves open when the walk with blockers stops and what it does when one right turn is still blocked; the rules below settle both.

Function Signature

def spiral_with_blockers(matrix: list[list[int]], blocked: list[list[int]]) -> list[int]:

Each entry of blocked is a blocker cell given as [row, col].

Rules

• Row 0 is the top row and column 0 is the leftmost column. From (r, c), right is (r, c + 1), down is (r + 1, c), left is (r, c - 1) and up is (r - 1, c). A clockwise turn changes right to down, down to left, left to up, and up to right.
• A cell is available when it is inside the matrix, is not a blocker, and has not been visited.
• The walk begins on (0, 0) facing right; (0, 0) is visited first and its value is output first.
• On each step, check the next cell in the current direction. If it is available, move there and output its value. Otherwise turn clockwise by 90 degrees and check again, trying at most four directions in all. The first direction with an available next cell becomes the current direction, and the walk moves one cell that way.
• When no direction from the current cell leads to an available cell, the walk stops. Open cells that were never reached do not appear in the output.
• Blockers never appear in the output.

Constraints

• 1 <= m, n <= 100, where m = len(matrix) and n = len(matrix[0]); all rows have length n.
• -10^9 <= matrix[r][c] <= 10^9
• 0 <= len(blocked) <= m * n - 1
• All blocker cells are inside the matrix and distinct, and [0, 0] is never a blocker.

Examples

Example 1

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], blocked = []
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

The ordinary spiral: the outer ring clockwise, then the center.

Example 2

Input: matrix = [[1, 2, 3], [4, 5, 6]], blocked = [[0, 1]]
Output: [1, 4, 5, 6, 3]

The blocker to the right of (0, 0) turns the walk down to 4. At (1, 0) facing down, down and left are outside the matrix and up is visited, so after three clockwise turns the walk faces right and moves through 5 to 6. At (1, 2) facing right, right and down are outside and left is visited, so it turns to face up and moves to 3. At (0, 2) every direction is outside, visited or the blocker, so the walk stops.

Example 3

Input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8]], blocked = [[1, 3]]
Output: [1, 2, 3, 4]

At (0, 3) facing right, right is outside, down is the blocker, left is visited and up is outside, so the walk stops before reaching the bottom row.