Repaint Arrows to Reach the Exit

Hard

You are given an m × n board. Each cell holds an arrow telling where to go next: - 1 means right, to arrows[i][j + 1]; - 2 means left, to arrows[i][j - 1]; - 3 means down, to arrows[i + 1][j]; - 4 means up, to arrows[i - 1][j]. An arrow may point off the board. A robot starts in the top-left cell (0, 0) and always follows the arrows exactly. It has to reach the bottom-right cell (m - 1, n - 1); the route does not need to be the shortest. The arrow in any cell can be repainted to any of the four directions at a cost of 1. Return the minimum number of repaints after which the robot reaches its goal.

Example 1

arrows=[[1, 3], [2, 2]] → 0

From (0, 0) we go right, from (0, 1) down, and we land in the bottom-right corner. No repainting is needed.

Example 2

arrows=[[4, 4], [4, 4]] → 2

Every arrow points up, off the board. Repaint (0, 0) to point right and (0, 1) to point down: two repaints.

Example 3

arrows=[[3, 1, 1], [1, 1, 4], [2, 2, 2]] → 1

Constraints

1 ≤ m, n ≤ 100
arrows[i][j] ∈ {1, 2, 3, 4}

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Graph Array Matrix Shortest Path Heap (Priority Queue)

Similar problems

Ball Into the Hole Hard Through the Walls to the Far Corner Hard Rooms on a Timer Hard Shortest Path of a Rolling Ball Medium Across the Hazard Field Medium

Input

arrows=[[1, 3], [2, 2]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.