列表

详情

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

这是一个交互问题。

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

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

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

GridMaster类存在以下功能：

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

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

测试实例:

测试输入一个大小为m x n的二维数组 grid 和四个int型参数 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
解释: 不存在可使机器人到达目标单元的路径。

 

提示:

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * // This is the GridMaster's API interface. * // You should not implement it, or speculate about its implementation * class GridMaster { * public: * bool canMove(char direction); * int move(char direction); * boolean isTarget(); * }; */ class Solution { public: int findShortestPath(GridMaster &master) { } };

python3 解法, 执行用时: 864 ms, 内存消耗: 32.7 MB, 提交时间: 2023-10-22 10:03:05 

# """
# 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 grid, directions, visited, findtarget, endx, endy

            visited.add((i, j))  # 加入已经访问
            if master.isTarget(): # 目标位置
                endx, endy = i, j
                findtarget = True

            for dx, dy, d, revd in directions:
                if (i+dx, j+dy) not in visited and master.canMove(d):
                    grid[i+dx][j+dy] = master.move(d) # 记录成本
                    dfs(i+dx, j+dy)
                    master.move(revd) # 回溯
            return

        grid = [[0 for _ in range(201)] for _ in range(201)]
        directions = [(0,1,"U","D"), (0,-1,"D","U"), (1,0,"L","R"), (-1,0,"R","L")]
        visited = set()
        findtarget = False
        endx, endy = -1, -1
        # 从初始位置 dfs搜索整个图 
        # 假设初始位置是在100,100 可以有效防止下标越界
        dfs(100,100)
        if not findtarget: # 没能找到target直接返回-1
            return -1

        # Dijkstra找到最短距离
        heap = [(0,100,100)] # 初始位置
        visited = set()
        while len(heap):
            cost, curx, cury = heapq.heappop(heap)
            if (curx, cury) == (endx, endy): # 找到了 
                return cost
            if (curx, cury) in visited: # 避免重复访问
                continue
            visited.add((curx, cury))  # 标记已经访问
            for dx, dy, _, _ in directions:
                nxtx, nxty = curx+dx, cury+dy 
                # 节点没有越界 可以访问且也没有被访问过
                if (0<=nxtx<=200 and 0 <=nxty<=200 and 
                    (nxtx, nxty) not in visited and 
                    grid[nxtx][nxty]): 
                    heapq.heappush(heap, (cost+grid[nxtx][nxty], nxtx, nxty))  # 加入最小堆
        return -1

python3 解法, 执行用时: 940 ms, 内存消耗: 37 MB, 提交时间: 2023-10-22 10:02:36 

# """
# 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:
#        
#

from queue import PriorityQueue

class Solution(object):
    def findShortestPath(self, master: 'GridMaster') -> int:

        vals = {}
        vals[(0, 0)] = 0

        t_i, t_j = None, None
        def dfs(ii, jj):
            nonlocal t_i, t_j
            if master.isTarget():
                t_i, t_j = ii, jj

            if (ii-1, jj) not in vals and master.canMove('U'):
                vals[(ii-1, jj)] = master.move('U')
                dfs(ii-1, jj)
                master.move('D')

            if (ii+1, jj) not in vals and master.canMove('D'):
                vals[(ii+1, jj)] = master.move('D')
                dfs(ii+1, jj)
                master.move('U')
                
            if (ii, jj-1) not in vals and master.canMove('L'):
                vals[(ii, jj-1)] = master.move('L')
                dfs(ii, jj-1)
                master.move('R')
                

            if (ii, jj+1) not in vals and master.canMove('R'):
                vals[(ii, jj+1)] = master.move('R')
                dfs(ii, jj+1)
                master.move('L')
                
        dfs(0, 0)
        if t_i is None:
            return -1;

        que = PriorityQueue()
        que.put((0, 0, 0))
        best = {}
        best[(0, 0)] = 0

        while que.qsize():
            cost, i, j = que.get()
            if (i,j) == (t_i, t_j):
                return cost

            for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if (ii, jj) in vals and ((ii, jj) not in best or cost + vals[(ii, jj)] < best[(ii, jj)]):
                    best[(ii, jj)] = cost + vals[(ii, jj)]
                    que.put((cost + vals[(ii, jj)], ii, jj))

        return -1

cpp 解法, 执行用时: 68 ms, 内存消耗: 17.6 MB, 提交时间: 2023-10-22 10:01:52 

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

class Solution {
public:
    char chs[4]={'U','D','L','R'};
    char antiChs[4]={'D','U','R','L'};
    int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    bool find = false;
    int targetX,targetY;
    int cost[200][200];


    void dfs(GridMaster& master,int x,int y){
        //判断是否为目标
        if(master.isTarget()){
            targetX = x;
            targetY = y;
            find = true;
        }
        for(int i =0;i<4;i++){
            //四个方向尝试能够走通
            if(master.canMove(chs[i])){
                //这个地方走过
                if(cost[x+d[i][0]][y+d[i][1]]>=0){
                    continue;
                }
                //标记这个节点的代价
                cost[x+d[i][0]][y+d[i][1]] = master.move(chs[i]);
                dfs(master,x+d[i][0],y+d[i][1]);
                master.move(antiChs[i]);
            }
        }
    }

    int findShortestPath(GridMaster &master) {
        
        
        //初始化所有结点的代价为负
        memset(cost,0XFF,sizeof(cost));
        //起点的代价为0
        cost[100][100] = 0;
        dfs(master,100,100);
        //不能到达最后一个结点
        if(!find){
            return -1;
        }
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
        q.push({0,{100,100}});
        int vis[200][200];
        memset(vis,0x3f,sizeof(vis));
        vis[100][100] = 0;
        int ans = 0;
        while(!q.empty()){
            auto item = q.top();
            q.pop();
            int curr_cost = item.first;

            int x = item.second.first;
            int y = item.second.second;
            //这个节点之前访问过
            if(vis[x][y]<curr_cost){
                continue;
            }
            //找到目标
            if(x==targetX&&y==targetY){
                ans = curr_cost;
                break;
            }

            for(int i =0;i<4;i++){
                int _x = x + d[i][0];
                int _y = y + d[i][1];
                //越界检查
                if(_x<0||_x>=200||_y<0||_y>=200){
                    continue;
                }
                //这个点不能访问 或者这个点通过其他路径的代价更低(或相同)
                if(cost[_x][_y]<0||vis[_x][_y]<=curr_cost+cost[_x][_y]){
                    continue;
                }
                //更新当前结点的最小访问代价
                vis[_x][_y] = curr_cost+cost[_x][_y];

                q.push({curr_cost+cost[_x][_y],{_x,_y}});
            }
        }
        return ans;
    }
};

cpp 解法, 执行用时: 64 ms, 内存消耗: 17.6 MB, 提交时间: 2023-10-22 10:01:24 

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


class Solution {
private:
    // 已知大小是100，那么数组最大就是200的范围, 表示每一格移动的成本
    int cost[200][200];
    // 四个方向
    char charDirs[4] = {'D', 'R', 'U', 'L'};
    // 反方向，回溯时候使用
    char charAntiDirs[4] = {'U', 'L', 'D', 'R'};
    // 对应x,y移动的变量，直接保存在一个数组里 
    int intDirs[5] = {0, 1, 0, -1, 0};

    // 目标对应的坐标
    int tx;
    int ty;

    struct Node
    {
        int distance;
        int x;
        int y;

        Node(int distance, int x, int y): distance(distance), x(x),y(y)
        {}

        // 小顶堆，距离越小在堆顶
        bool operator< (const Node &b) const
        {
            return distance > b.distance;
        }
    };

    // 构建图的dfs
    void dfs(GridMaster& master, int x, int y)
    {
        // 判断是否是目标
        if (master.isTarget())
        {
            tx = x;
            ty = y;
        }
        // 四个方向去尝试
        for (int i = 0; i < 4; ++i)
        {
            if (master.canMove(charDirs[i]))
            {
                // 只考虑没有遍历过的
                int nx = x+intDirs[i];
                int ny = y+intDirs[i+1];
                if (cost[nx][ny] < 0)
                {
                    cost[nx][ny] = master.move(charDirs[i]);
                    // cout << nx << "," << ny << " " << cost[nx][ny] << endl;
                    dfs(master, nx, ny);
                    // 回溯回去尝试下一种方向
                    master.move(charAntiDirs[i]);
                }
            }
        }
    }

public:
    int findShortestPath(GridMaster &master) {
        // 默认目标为负值无效
        tx = -1;
        ty = -1;
        // 设置cost为-1作为默认值
        memset(cost, 0xff, sizeof(int)*200*200);
        
        // 起点就是200的中点 100，100
        cost[100][100] = 0; 
        dfs(master, 100, 100);

        // 判断是否能到终点
        if (tx == -1 || ty == -1)
        {
            return -1;
        }

        // 记录已经遍历的距离
        int distances[200][200];
        memset(distances, 0x3f3f3f3f, sizeof(distances));
         
        priority_queue<Node> q;

        // 起点距离为0
        distances[100][100] = 0;
        q.emplace(0, 100, 100);

        while (!q.empty())
        {
            auto& curr = q.top();
            int dist = curr.distance;
            int x = curr.x;
            int y = curr.y;
            q.pop();

            // 忽略距离更大的情况
            if (dist <= distances[x][y])
            {
                if (x == tx && y == ty)
                {
                    // 找到终点直接返回
                    return dist;
                }

                // 四个方向去遍历
                for (int i = 0; i < 4; ++i)
                {
                    int nx = x + intDirs[i];
                    int ny = y + intDirs[i+1];
                    // 保证可达，且距离更小 
                    if (nx >= 0 && nx < 200 && ny >= 0 && ny < 200 && cost[nx][ny] >= 0)
                    {
                        if (distances[nx][ny] > dist + cost[nx][ny])
                        {
                            distances[nx][ny] = dist + cost[nx][ny];
                            q.emplace(distances[nx][ny] , nx, ny);
                        }
                    }
                }
            }
        }

        return 0;
    }   
};

上一题

© 2024 leetcode.cn