Skip to content

Latest commit

 

History

History
258 lines (213 loc) · 8.76 KB

README.md

File metadata and controls

258 lines (213 loc) · 8.76 KB
Raw
comments difficulty edit_url tags
true
中等
深度优先搜索
广度优先搜索
图
交互
堆（优先队列）

1810. 隐藏网格下的最小消耗路径 🔒

English Version

题目描述

这是一个交互问题。

有一个机器人存在于网格中，你需要通过不断尝试使他从初始单元到达目标单元。网格的规格为m x n，并且每个单元的属性值要不为空，要不已被占用。题目保证初始网格和目标网格不同且均为空。

每个单元格都有消耗值，你需要在每次移动至此单元格后支付该费用。在机器人启动前，初始单元的费用不被计算在内。

你需要找到机器人移动至目标网格的最小总消耗。但可惜的是你并不知道网格的尺寸、初始单元和目标单元。你只允许通过询问GridMaster类获得信息。

GridMaster类存在以下功能：

  • boolean canMove(char direction) 当机器人可以向这个方向移动时，返回true；反之返回false。
  • int move(char direction) 沿该方向移动机器人，并返回移动到该单元的消耗值。如果此移动将机器人移动到被占有的单元格或离开网格，则移动将被忽略，机器人将保持在相同的位置，函数将返回-1。
  • boolean isTarget() ：如果机器人当前位于目标单元格上，则返回true；反之返回 false 。

请注意，上述函数中的方向应该是{ 'U'、'D'、'L'、'R' }中的字符，分别表示向上、向下、左和右方向。

返回使机器人从其初始起始单元到目标单元的最小总消耗。如果单元格之间不存在有效路径，则返回-1。

测试实例:

测试输入一个大小为m x n的二维数组 grid 和四个int型参数 r1, c1, r2, 和 c2 :

  • grid[i][j] == 0 表示网格 (i, j) 已被占用。
  • grid[i][j] >= 1 表示网格单元 (i, j) 为空并且 grid[i][j] 的值为移动至此网格的成本值。
  • (r1, c1) 为初始单元。
  • (r2, c2) 为目标单元。

请注意，你将无法在你的代码中获知这些信息。

 

示例 1:

输入: grid = [[2,3],[1,1]], r1 = 0, c1 = 1, r2 = 1, c2 = 0
输出: 2
解释: 其中一种可能路径描述如下：
机器人最开始站在单元格 (0, 1) ，用 3 表示
- master.canMove('U') 返回 false
- master.canMove('D') 返回 true
- master.canMove('L') 返回 true
- master.canMove('R') 返回 false
- master.move('L') 机器人移动到单元格 (0, 0) 并返回 2
- master.isTarget() 返回 false
- master.canMove('U') 返回 false
- master.canMove('D') 返回 true
- master.canMove('L') 返回 false
- master.canMove('R') 返回 true
- master.move('D') 机器人移动到单元格 (1, 0) 并返回 1
- master.isTarget() 返回 true
- master.move('L') 机器人不移动并返回 -1
- master.move('R') 机器人移动到单元格 (1, 1) 并返回 1
现在我们知道了机器人达到目标单元(1, 0)的最小消耗成本为2。

示例 2:

输入: grid = [[0,3,1],[3,4,2],[1,2,0]], r1 = 2, c1 = 0, r2 = 0, c2 = 2
输出: 9
解释: 最小消耗路径为 (2,0) -> (2,1) -> (1,1) -> (1,2) -> (0,2).

示例 3:

输入: grid = [[1,0],[0,1]], r1 = 0, c1 = 0, r2 = 1, c2 = 1
输出: -1
解释: 不存在可使机器人到达目标单元的路径。

 

提示:

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

解法

方法一：DFS 建图 + 堆优化版 Dijkstra 算法

Python3

# """
# This is GridMaster's API interface.
# You should not implement it, or speculate about its implementation
# """
# class GridMaster(object):
#    def canMove(self, direction: str) -> bool:
#
#
#    def move(self, direction: str) -> int:
#
#
#    def isTarget(self) -> None:
#
#


class Solution(object):
    def findShortestPath(self, master: 'GridMaster') -> int:
        def dfs(i, j):
            nonlocal target
            if master.isTarget():
                target = (i, j)
            for dir, (a, b, ndir) in dirs.items():
                x, y = i + a, j + b
                if 0 <= x < N and 0 <= y < N and master.canMove(dir) and g[x][y] == -1:
                    g[x][y] = master.move(dir)
                    dfs(x, y)
                    master.move(ndir)

        target = (-1, -1)
        N = 200
        INF = 0x3F3F3F3F
        g = [[-1] * N for _ in range(N)]
        dirs = {
            'U': (-1, 0, 'D'),
            'D': (1, 0, 'U'),
            'L': (0, -1, 'R'),
            'R': (0, 1, 'L'),
        }
        dfs(100, 100)
        if target == (-1, -1):
            return -1
        q = [(0, 100, 100)]
        dist = [[INF] * N for _ in range(N)]
        dist[100][100] = 0
        while q:
            w, i, j = heappop(q)
            if (i, j) == target:
                return w
            for a, b, _ in dirs.values():
                x, y = i + a, j + b
                if (
                    0 <= x < N
                    and 0 <= y < N
                    and g[x][y] != -1
                    and dist[x][y] > w + g[x][y]
                ):
                    dist[x][y] = w + g[x][y]
                    heappush(q, (dist[x][y], x, y))
        return 0

Java

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *     boolean canMove(char direction);
 *     int move(char direction);
 *     boolean isTarget();
 * }
 */

class Solution {
    private static final char[] dir = {'U', 'R', 'D', 'L'};
    private static final char[] ndir = {'D', 'L', 'U', 'R'};
    private static final int[] dirs = {-1, 0, 1, 0, -1};
    private static final int N = 200;
    private static final int INF = 0x3f3f3f3f;
    private static int[][] g = new int[N][N];
    private static int[][] dist = new int[N][N];
    private int[] target;

    public int findShortestPath(GridMaster master) {
        target = new int[] {-1, -1};
        for (int i = 0; i < N; ++i) {
            Arrays.fill(g[i], -1);
            Arrays.fill(dist[i], INF);
        }
        dfs(100, 100, master);
        if (target[0] == -1 && target[1] == -1) {
            return -1;
        }
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        q.offer(new int[] {0, 100, 100});
        dist[100][100] = 0;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int w = p[0], i = p[1], j = p[2];
            if (i == target[0] && j == target[1]) {
                return w;
            }
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                if (x >= 0 && x < N && y >= 0 && y < N && g[x][y] != -1
                    && dist[x][y] > w + g[x][y]) {
                    dist[x][y] = w + g[x][y];
                    q.offer(new int[] {dist[x][y], x, y});
                }
            }
        }
        return 0;
    }

    private void dfs(int i, int j, GridMaster master) {
        if (master.isTarget()) {
            target = new int[] {i, j};
        }
        for (int k = 0; k < 4; ++k) {
            char d = dir[k], nd = ndir[k];
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < N && y >= 0 && y < N && master.canMove(d) && g[x][y] == -1) {
                g[x][y] = master.move(d);
                dfs(x, y, master);
                master.move(nd);
            }
        }
    }
}