LeetCode 1368. 使网格图至少有一条有效路径的最小代价

Categories:

题目描述
思路分析
1. 解法一：0-1 BFS（推荐）
相似题目

题目描述

✅ 1368. 使网格图至少有一条有效路径的最小代价

思路分析

解法一：0-1 BFS（推荐）

核心思路：

每个格子有默认方向，沿默认方向走代价为 0，否则为 1。

使用 0-1 BFS：代价为 0 的边入队头，代价为 1 的边入队尾。

最终得到左上到右下的最小代价。

复杂度分析：

时间复杂度：O(mn)。

空间复杂度：O(mn)。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Deque<int[]> dq = new ArrayDeque<>();
        dist[0][0] = 0;
        dq.offerFirst(new int[] {0, 0});

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int x = cur[0];
            int y = cur[1];
            int d = dist[x][y];

            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                int cost = (grid[x][y] == i + 1) ? 0 : 1;
                if (d + cost < dist[nx][ny]) {
                    dist[nx][ny] = d + cost;
                    if (cost == 0) {
                        dq.offerFirst(new int[] {nx, ny});
                    } else {
                        dq.offerLast(new int[] {nx, ny});
                    }
                }
            }
        }

        return dist[m - 1][n - 1];
    }
}

import "container/list"

func minCost(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dist := make([][]int, m)
    for i := 0; i < m; i++ {
        dist[i] = make([]int, n)
        for j := 0; j < n; j++ {
            dist[i][j] = 1 << 30
        }
    }

    dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    type Node struct {
        x int
        y int
    }

    dq := list.New()
    dist[0][0] = 0
    dq.PushFront(Node{0, 0})

    for dq.Len() > 0 {
        e := dq.Front()
        dq.Remove(e)
        cur := e.Value.(Node)
        d := dist[cur.x][cur.y]

        for i := 0; i < 4; i++ {
            nx := cur.x + dirs[i][0]
            ny := cur.y + dirs[i][1]
            if nx < 0 || nx >= m || ny < 0 || ny >= n {
                continue
            }
            cost := 1
            if grid[cur.x][cur.y] == i+1 {
                cost = 0
            }
            if d+cost < dist[nx][ny] {
                dist[nx][ny] = d + cost
                if cost == 0 {
                    dq.PushFront(Node{nx, ny})
                } else {
                    dq.PushBack(Node{nx, ny})
                }
            }
        }
    }

    return dist[m-1][n-1]
}

相似题目

题目	难度	考察点
743. 网络延迟时间	中等	最短路
1631. 最小体力消耗路径	中等	最短路
778. 水位上升的泳池中游泳	困难	最短路
1976. 到达目的地的方案数	中等	最短路
1514. 概率最大的路径	中等	最短路

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/35926189