Hard

题目描述

给你一个 m x n 的网格图 grid 。网格中每个格子都有一个方向标志，指向你应该访问的下一个格子。格子 grid[i][j] 中的标志可能为：

  • 1 ：下一个格子是右边的格子，即你会从 grid[i][j] 走到 grid[i][j + 1]
  • 2 ：下一个格子是左边的格子，即你会从 grid[i][j] 走到 grid[i][j - 1]
  • 3 ：下一个格子是下边的格子，即你会从 grid[i][j] 走到 grid[i + 1][j]
  • 4 ：下一个格子是上边的格子，即你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格中可能会有指向网格外面的标志。

你将从左上角的格子 (0, 0) 开始出发。网格中的「有效路径」是指从左上角格子 (0, 0) 开始、一直到右下角 (m - 1, n - 1) 结束，且路径中每一步都按照路标的方向前进的路径。有效路径不需要是最短路径。

你可以花费 cost = 1 的代价修改一个格子中的标志（修改一次）。

请你返回让网格中至少有一条有效路径的最小代价。

示例 1：

输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 1 使方向向下  --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 1 使方向向下 --> (3, 3)
总代价 = 3.

示例 2：

输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
输出：0
解释：不修改标志你就可以从 (0, 0) 到达 (2, 2) 。

示例 3：

输入：grid = [[1,2],[4,3]]
输出：1

提示：

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

解题思路

这是一个典型的最短路径问题，需要用到0-1 BFS算法。

核心思路：

  1. 将网格看作图，每个格子可以向四个方向移动
  2. 如果当前格子的方向标志指向目标格子，则移动代价为0；否则需要修改标志，代价为1
  3. 使用双端队列进行BFS：代价为0的路径加入队头，代价为1的路径加入队尾
  4. 这样保证了队列中的元素按代价递增排列，第一次到达终点的路径就是最小代价

算法步骤：

  1. 初始化方向数组，对应四个方向的移动
  2. 使用双端队列，从起点(0,0)开始，代价为0
  3. 对于当前位置，检查四个方向：
    • 如果是当前格子标志指向的方向，代价为0，加入队头
    • 否则代价为1，加入队尾
  4. 当第一次到达终点时，返回当前代价

推荐解法：0-1 BFS 时间复杂度O(mn)，空间复杂度O(mn)，是此类问题的最优解法。

代码实现

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        vector<vector<int>> cost(m, vector<int>(n, INT_MAX));
        deque<pair<int, int>> dq;
        
        dq.push_back({0, 0});
        cost[0][0] = 0;
        
        while (!dq.empty()) {
            auto [x, y] = dq.front();
            dq.pop_front();
            
            if (x == m - 1 && y == n - 1) {
                return cost[x][y];
            }
            
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newCost = cost[x][y] + (grid[x][y] != d + 1);
                    
                    if (newCost < cost[nx][ny]) {
                        cost[nx][ny] = newCost;
                        if (grid[x][y] == d + 1) {
                            dq.push_front({nx, ny});
                        } else {
                            dq.push_back({nx, ny});
                        }
                    }
                }
            }
        }
        
        return cost[m - 1][n - 1];
    }
};

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        from collections import deque
        
        m, n = len(grid), len(grid[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        cost = [[float('inf')] * n for _ in range(m)]
        dq = deque()
        
        dq.append((0, 0))
        cost[0][0] = 0
        
        while dq:
            x, y = dq.popleft()
            
            if x == m - 1 and y == n - 1:
                return cost[x][y]
            
            for d in range(4):
                nx, ny = x + dirs[d][0], y + dirs[d][1]
                
                if 0 <= nx < m and 0 <= ny < n:
                    new_cost = cost[x][y] + (0 if grid[x][y] == d + 1 else 1)
                    
                    if new_cost < cost[nx][ny]:
                        cost[nx][ny] = new_cost
                        if grid[x][y] == d + 1:
                            dq.appendleft((nx, ny))
                        else:
                            dq.append((nx, ny))
        
        return cost[m - 1][n - 1]

public class Solution {
    public int MinCost(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[,] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int[,] cost = new int[m, n];
        var dq = new LinkedList<(int, int)>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cost[i, j] = int.MaxValue;
            }
        }
        
        dq.AddLast((0, 0));
        cost[0, 0] = 0;
        
        while (dq.Count > 0) {
            var (x, y) = dq.First.Value;
            dq.RemoveFirst();
            
            if (x == m - 1 && y == n - 1) {
                return cost[x, y];
            }
            
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d, 0];
                int ny = y + dirs[d, 1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newCost = cost[x, y] + (grid[x][y] == d + 1 ? 0 : 1);
                    
                    if (newCost < cost[nx, ny]) {
                        cost[nx, ny] = newCost;
                        if (grid[x][y] == d + 1) {
                            dq.AddFirst((nx, ny));
                        } else {
                            dq.AddLast((nx, ny));
                        }
                    }
                }
            }
        }
        
        return cost[m - 1, n - 1];
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minCost = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    const deque = [[0, 0, 0]]; // [row, col, cost]
    const visited = new Set();
    
    while (deque.length > 0) {
        const [row, col, cost] = deque.shift();
        
        if (row === m - 1 && col === n - 1) {
            return cost;
        }
        
        const key = `${row},${col}`;
        if (visited.has(key)) continue;
        visited.add(key);
        
        for (let dir = 0; dir < 4; dir++) {
            const [dx, dy] = directions[dir];
            const newRow = row + dx;
            const newCol = col + dy;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                const newKey = `${newRow},${newCol}`;
                if (!visited.has(newKey)) {
                    const needsChange = grid[row][col] !== dir + 1;
                    const newCost = cost + (needsChange ? 1 : 0);
                    
                    if (needsChange) {
                        deque.push([newRow, newCol, newCost]);
                    } else {
                        deque.unshift([newRow, newCol, newCost]);
                    }
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度0-1 BFS
时间复杂度O(mn)
空间复杂度O(mn)

说明：

  • 时间复杂度：每个格子最多被访问常数次，总共mn个格子
  • 空间复杂度：需要存储每个格子的最小代价，以及双端队列的空间

相关题目