Solve BFS and grid tasks

The coding rounds included several algorithmic problems:

1. Threshold search with binary search: You are given floors 1..n and an API canOperate(floor) that returns true if an elevator can safely serve that floor and false otherwise. There exists a highest safe floor T such that all floors <= T are safe and all floors > T are unsafe. Find T using O(log n) calls.

2. Shortest path on a combination lock: A lock has four wheels, each showing a digit 0-9. In one move, you may increment or decrement exactly one wheel by 1, with wraparound (9 -> 0, 0 -> 9). Given a start state, a target state, and a set of blocked states that cannot be visited, return the minimum number of moves needed to reach the target, or -1 if it is impossible.

3. Nearest exit in a 2D grid: You are given a rectangular grid containing walls and open cells, plus a starting cell inside the grid. You may move up, down, left, or right through open cells. Return the minimum number of steps needed to reach any open boundary cell other than the starting cell, or -1 if no exit exists.

4. Generate a random minesweeper board: Given rows, cols, and N, generate a rows x cols board with exactly N mines placed uniformly at random in distinct cells. Then fill each non-mine cell with the number of adjacent mines in the eight neighboring positions. The implementation should emphasize clean code, simple logic, and avoidance of unnecessary auxiliary data structures when possible.

Part 1: Highest Safe Floor

You are given a monotonic boolean list safe where safe[i] tells whether floor i + 1 is safe for an elevator. There exists a threshold T such that every floor 1..T is safe (True) and every floor T+1..n is unsafe (False). Return the highest safe floor number T. If no floor is safe, return 0. Your algorithm should use binary search.

Constraints

• 0 <= len(safe) <= 200000
• The list is monotonic: all True values come before all False values
• Floor numbers are 1-based

Examples

Example 1

Input: []
Output: 0

Explanation: There are no floors, so the highest safe floor is 0.

Example 2

Input: [True]
Output: 1

Explanation: The only floor is safe.

Hints

1. This is equivalent to finding the index of the last True value.
2. If you know how to find the first False, you can derive the answer from that too.

Part 2: Shortest Path on a Combination Lock

A lock has four wheels, each showing a digit from 0 to 9. A state is a 4-character string such as '0294'. In one move, you may increment or decrement exactly one wheel by 1, with wraparound (9 -> 0 and 0 -> 9). Given a start state, a target state, and a list of blocked states that cannot be visited, return the minimum number of moves needed to reach the target. Return -1 if it is impossible.

Constraints

• start and target are 4-character strings of digits
• 0 <= len(deadends) <= 10000
• All blocked states are unique

Examples

Example 1

Input: ('0000', '0202', ['0201', '0101', '0102', '1212', '2002'])
Output: 6

Explanation: A shortest valid path reaches the target in 6 moves.

Example 2

Input: ('0000', '8888', ['0001', '0010', '0100', '1000', '0009', '0090', '0900', '9000'])
Output: -1

Explanation: All immediate neighbors of the start are blocked, so no move is possible.

Hints

1. Each lock state is a node in an unweighted graph, so think BFS.
2. From one state, there are exactly 8 next states: for each of 4 wheels, rotate up or down.

Part 3: Nearest Exit in a 2D Grid

You are given a rectangular maze containing walls '+' and open cells '.', plus a starting cell entrance. You may move up, down, left, or right through open cells only. An exit is any open boundary cell other than the starting cell itself. Return the minimum number of steps needed to reach any exit, or -1 if no exit exists.

Constraints

• 1 <= number of rows, columns <= 200
• maze[entrance[0]][entrance[1]] is '.'
• Moves are allowed only in the four cardinal directions

Examples

Example 1

Input: ([['+','+','.','+'],['.','.','.','+'],['+','+','+','.']], (1, 2))
Output: 1

Explanation: The cell (0, 2) is an exit and is one step away.

Example 2

Input: ([['+','+','+'],['.','.','.'],['+','+','+']], (1, 0))
Output: 2

Explanation: The entrance is on the boundary but does not count; the nearest other exit is (1, 2).

Hints

1. Because every move costs the same, BFS gives the shortest path.
2. Do not count the entrance as an exit even if it lies on the boundary.

Part 4: Seeded Minesweeper Board Generation

Generate a Minesweeper board with exactly N mines in a rows x cols grid, then fill each non-mine cell with the number of adjacent mines in the 8 surrounding cells. In a real game, the mine positions would be chosen uniformly at random. To make this problem deterministic for testing, use this exact seeded shuffle to choose distinct mine cells: start with cells = [0, 1, ..., rows*cols-1] and x = seed. For i from rows*cols-1 down to 1, update x = (x * 31 + 7) % 9973, set j = x % (i + 1), and swap cells[i] with cells[j]. The first N values in cells are mine positions. Convert a flat index p to (p // cols, p % cols). Return a 2D list containing '*' for mines and integers for counts.

Constraints

• 1 <= rows, cols <= 50
• 0 <= N <= rows * cols
• Use the exact seeded shuffle described in the statement

Examples

Example 1

Input: (1, 1, 0, 5)
Output: [[0]]

Explanation: A 1x1 board with no mines contains a single 0.

Example 2

Input: (2, 2, 4, 0)
Output: [['*', '*'], ['*', '*']]

Explanation: When every cell is a mine, the whole board is filled with '*'.

Hints

1. A flat index p maps to row p // cols and column p % cols.
2. After marking all mines, loop over the mines and increment each valid neighbor if it is not a mine.