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
- The cost of moving in the cell's own direction is 0; any other direction costs 1.
- So this is another 0-1 BFS over the cells.
- For each cell, try all four directions; the weight is
0when it matches the stored arrow. - 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
dirsorder. - 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.