题目

给定一个二维的 m × n 网格地图（grids二维数组），每个单元格 0 为空，1 是障碍物，2 是红绿灯；每一步可以在 0 或者 2 的单元格移动，每秒可以走一个单元格，遇到红绿灯想要通过需要等待不同的时间才能通过，大小为 x 的 light 数组标注灯的坐标和等待时间，例如 (2,2,3)，坐标 (2,2) 红绿灯等待时间 3 秒，问从左上角 (0,0) 到右下角 (m-1,n-1) 所需的最短时间。

输入描述

第一行输入 grids 二维数组，内部数据只有 0，1，2，1 < m, n <= 100

第二行输入 lights 红绿灯二维数组，1 < x <= m × n

输出描述

从坐标 (0,0) 到 (m-1,n-1) 坐标所需的最短时间，如果没有路径，则返回最短时间为 -1。

示例1

输入

[[0,1,0],[0,2,1],[0,0,0]]
[[1,1,3]]

输出

4

解题思路

建模

  1. 图的节点：网格中的 (x,y)。

  2. 图的边：4个方向移动。

  3. 边的权重：每移动 1 格耗时 1 秒，如果是红绿灯则再加上等待时间。

  4. 状态：dist 数组，存放从 (0,0) 点出发的最小权重路径的长度。每移动 1 格耗时 1 秒，如果是红绿灯则再加上等待时间。

  5. 起点：(0, 0)

  6. 目标：(m-1, n-1)

解法范式

本题是带权图且权重>1，即带权最短路径问题，用 Dijkstra 算法。

单源、带权图且权重 > 0 的，用 Dijkstra。
带权图且权重可能 < 0 的，用 Bellman-Ford。
要算所有点对最短路的，用 Floyd。
BFS就是权等于1的特殊情况下的 Dijkstra。

关键点

  1. 设计状态：dist[x][y] = 从 (0,0) 到 (x,y) 的最短时间

  2. 状态转移（松弛）：
    从 (x,y) 扩展到 (nx,ny)：

    newTime = dist[x][y] + 1
if (nx,ny) 是红绿灯:
    newTime += waitTime[nx][ny]

    然后做标准 Dijkstra 松弛：

    if newTime < dist[nx][ny]:
    更新

  3. 优先队列：存放每一次松弛的所有邻居，从队列中取出的一定是最优解。

  4. dist 初始化：

    // 初始化 dist
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
    Arrays.fill(dist[i], Integer.MAX_VALUE);
}
dist[0][0] = 0;

  1. 输入处理：

    // 初始化路灯，转化为二维数组。
private void parseLight(String input, int[][] lights) {
    input = input.substring(2, input.length() - 2);
    String[] rows = input.split("\\],\\[");
    for (String row : rows) {
        String[] nums = row.split(",");
        int x = Integer.parseInt(nums[0]);
        int y = Integer.parseInt(nums[1]);
        int time = Integer.parseInt(nums[2]);
        lights[x][y] = time;
    }
}
// 初始化网格
private static int[][] parseGrid(String input) {
    input = input.substring(2, input.length() - 2);
    String[] rows = input.split("\\],\\[");
    int m = rows.length;
    int n = rows[0].split(",").length;
    int[][] grid = new int[m][n];
    for (int i = 0; i < m; i++) {
        String[] nums = rows[i].split(",");
        for (int j = 0; j < n; j++) {
            grid[i][j] = Integer.parseInt(nums[j]);
        }
    }
    return grid;
}

代码

package com.huaweiod.c.completed;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class GridTrafficLightShortestPath {

    public static int solution(int[][] grids, int[][] lights) {
        int m = grids.length;
        int n = grids[0].length;
        // 初始化 dist，dist 表示(x,y)距离原点最短距离，全部初始化为无穷大。
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;

        // 初始化优先队列，存放(x, y, dist[x][y])，优先队列中用于对比大小的数据为 dist 数组，即
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        if (grids[0][0] == 2) {
            dist[0][0] += lights[0][0];
        }
        pq.offer(new int[]{0, 0, dist[0][0]});

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], time = cur[2];
            // 剪枝：不是最优，直接舍弃
            if (time > dist[x][y]) {
                continue;
            }
            // 到达终点，直接返回
            if (x == m - 1 && y == n - 1) {
                return time;
            }
            // 四个方向扩展
            for (int[] dir : dirs) {
                int nx = dir[0] + x, ny = dir[1] + y;
                // 越界
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                // 障碍物
                if (grids[nx][ny] == 1) {
                    continue;
                }
                // 基础移动时间
                int newTime = time + 1;
                // 遇到红绿灯
                if (grids[nx][ny] == 2) {
                    newTime += lights[nx][ny];
                }
                // 松弛
                if (newTime < dist[nx][ny]) {
                    dist[nx][ny] = newTime;
                    pq.offer(new int[]{nx, ny, newTime});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] grids = parseGrid(sc.nextLine());
        int[][] lights = new int[grids.length][grids[0].length];
        parseLight(sc.nextLine(), lights);
        int time = solution(grids, lights);
        System.out.println(time);
    }

    private static void parseLight(String input, int[][] lights) {
        input = input.substring(2, input.length() - 2);
        String[] rows = input.split("\\],\\[");
        for (String row : rows) {
            String[] nums = row.split(",");
            int x = Integer.parseInt(nums[0]);
            int y = Integer.parseInt(nums[1]);
            int time = Integer.parseInt(nums[2]);
            lights[x][y] = time;
        }
    }

    private static int[][] parseGrid(String input) {
        input = input.substring(2, input.length() - 2);
        String[] rows = input.split("\\],\\[");
        int m = rows.length;
        int n = rows[0].split(",").length;
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            String[] nums = rows[i].split(",");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(nums[j]);
            }
        }
        return grid;
    }
}