Minimum Cost to Make at Least One Valid Path in a Grid

HardGraphs0-1 bfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n grid where every cell holds an arrow telling you where to move next: 1 means right, 2 means left, 3 means down and 4 means up. Some arrows may point outside the grid. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1) by repeatedly following the arrow in your current cell. You may change the arrow in any cell, at a cost of 1 per change, and each cell can be changed at most once. Return the minimum total cost needed so that following the arrows from (0, 0) reaches (m - 1, n - 1). If the start is the destination, the answer is 0.

Examples

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Follow row 0 to (0,3) and flip it down (cost 1), follow row 1 left to (1,0) and flip it down (cost 2), follow row 2 to (2,3) and flip it down (cost 3), arriving at (3,3).
Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Right, right, down, left, left, down, right, right: the arrows already lead to the corner.
Input: grid = [[1,2],[4,3]]
Output: 1
Change (0,1) from left to down and the path (0,0) -> (0,1) -> (1,1) works.

Constraints

  • m == grid.length, n == grid[i].length
  • 1 <= m, n <= 100
  • 1 <= grid[i][j] <= 4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.