# 1810. Minimum Path Cost in a Hidden Grid
###### tags: `Leetcode` `Medium` `Dijkstra` `DFS`
Link: https://leetcode.com/problems/minimum-path-cost-in-a-hidden-grid/
## 思路
先dfs建图 然后dijkstra
## Code

class Solution {
    int[][] dirs = new int[][]{{-1,0},{0,1},{0,-1},{1,0}};
    char[] charDir = new char[]{'U', 'R', 'L', 'D'};
    int[] target;
    int edge = 201;
    public int findShortestPath(GridMaster master) {
        int[][] map = new int[edge][edge];
        boolean[][] visited = new boolean[edge][edge];
        visited[edge/2][edge/2] = true;
        dfs(master, map, visited, edge/2, edge/2);
        if(target==null) return -1;
        return dijk(master, map, edge/2, edge/2);
    }
    
    private void dfs(GridMaster master, int[][] map, boolean[][] visited, int x, int y){ 
        if(master.isTarget()){
            target = new int[]{x,y};
        }
        for(int i=0; i<dirs.length; i++){
            int[] dir = dirs[i];
            int nextx = x+dir[0];
            int nexty = y+dir[1];
            if(master.canMove(charDir[i]) && !visited[nextx][nexty]){
                map[nextx][nexty] = master.move(charDir[i]);
                visited[nextx][nexty] = true;
                dfs(master, map, visited, nextx, nexty);
                master.move(charDir[3-i]);
            }
        }
    }
    private int dijk(GridMaster master, int[][] map, int x, int y){
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[2]-b[2]));
        Integer[][] cost = new Integer[edge][edge];
        pq.add(new int[]{x,y,0});
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            if(curr[0]==target[0] && curr[1]==target[1]) return cost[curr[0]][curr[1]];
            for(int[] dir:dirs){
                int nextx = curr[0]+dir[0];
                int nexty = curr[1]+dir[1];
                if(nextx>=0 && nextx<edge && nexty>=0 && nexty<edge && map[nextx][nexty]!=0){
                    int dist = curr[2]+map[nextx][nexty];
                    if(cost[nextx][nexty]==null || dist<cost[nextx][nexty]){
                        cost[nextx][nexty] = dist;
                        pq.add(new int[]{nextx, nexty, cost[nextx][nexty]});
                    }
                }
            }
        }
        return -1;
    }
}