⚡Flashcard Drill➔
NeetCode #637LC-1368HardAdvanced Graphs
← Back to All Problems

#637 · #1368 · Minimum Cost to Make at Least One Valid Path in a Grid(使网格图至少有一条有效路径的最小代价)

📌 Problem Statement & Constraints

You are given an m x n grid where each cell holds an arrow direction (1 = right, 2 = left, 3 = down, 4 = up). You may modify any cell's arrow at cost 1. Return the minimum cost to make at least one valid path from the top-left to the bottom-right. Constraints: 1 <= m, n <= 100.

💡 Core Algorithmic Approaches

  1. The cost of moving in the cell's own direction is 0; any other direction costs 1.
  2. So this is another 0-1 BFS over the cells.
  3. For each cell, try all four directions; the weight is 0 when it matches the stored arrow.
  4. The answer is the distance at the bottom-right cell.

💻 Benchmark Python3 Implementation

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        from collections import deque
        m, n = len(grid), len(grid[0])
        # direction index 1..4 matches the grid encoding
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        INF = float("inf")
        dist = [[INF] * n for _ in range(m)]
        dist[0][0] = 0
        dq = deque([(0, 0)])
        while dq:
            r, c = dq.popleft()
            for i, (dr, dc) in enumerate(dirs, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    w = 0 if i == grid[r][c] else 1   # free when following the arrow
                    if dist[r][c] + w < dist[nr][nc]:
                        dist[nr][nc] = dist[r][c] + w
                        if w == 0:
                            dq.appendleft((nr, nc))
                        else:
                            dq.append((nr, nc))
        return dist[m - 1][n - 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): 0-1 BFS is linear.
💾 Space Complexity
O(m * n) for the distance grid and the deque.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing the direction index with the arrow value incorrectly: the encoding is 1 = right, 2 = left, 3 = down, 4 = up, matching the dirs order.
  • Using Dijkstra with a heap: correct but slower than 0-1 BFS.
  • Charging 1 for the matching direction: the cost is 0 when the arrow already points that way.
  • Forgetting that modifying a cell is a one-time cost: the model charges per move, which is equivalent because a cell is left once.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems