773 Sliding Puzzle

class Solution {
    private class Node{
        int[][] board;
        String hash;
        int zero_x;
        int zero_y;
        int depth;

        public Node(int[][] b, int r, int c, int dep){
            board = b;
            hash = Arrays.deepToString(b);
            zero_x = r;
            zero_y = c;
            depth = dep;
        }
    }

    public int slidingPuzzle(int[][] board) {
        if (board == null || board.length == 0) return -1;

        int n = board.length, m = board[0].length;
        // find position of 0
        int sr = 0;
        int sc = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (board[i][j] == 0){
                    sr = i;
                    sc = j;
                }
            }
        }

        Queue<Node> q = new LinkedList<>();
        Set<String> seen = new HashSet<>();
        int[][] targetBoard = new int[][]{{1, 2, 3}, {4, 5, 0}};
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        String target = Arrays.deepToString(targetBoard);

        Node src = new Node(board, sr, sc, 0);
        q.offer(src);
        seen.add(src.hash);

        //System.out.println("src: " + src.hash);
        //System.out.println("target: " + target);

        while (!q.isEmpty()){
            //System.out.println("in here");
            Node cur = q.poll();
            System.out.println("cur x: " + cur.zero_x + " cur y: " + cur.zero_y);
            if (cur.hash.equals(target)) return cur.depth;

            for (int k = 0; k < 4; k++){
                int xx = cur.zero_x + dirs[k][0];
                int yy = cur.zero_y + dirs[k][1];

                if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;

                //System.out.println("in here, x: " + xx + " yy: " + yy);
                int[][] newBoard = new int[n][m];
                for (int i = 0; i < n; i++){
                    for (int j = 0; j < m; j++){
                        newBoard[i][j] = cur.board[i][j];
                    }
                }
                newBoard[cur.zero_x][cur.zero_y] = newBoard[xx][yy];
                newBoard[xx][yy] = 0;

                Node newNode = new Node(newBoard, xx, yy, cur.depth + 1);

                if (seen.contains(newNode.hash)) continue;

                seen.add(newNode.hash);
                q.offer(newNode);

                //System.out.println("new node: " + newNode.hash);
            }
        }

        return -1;
    }
}

787 Cheapest Flights Within K Stops

经典 Dijkstra's

class Solution {
    private class Node{
        int index, depth, cost;

        public Node(int i, int d, int c){
            index = i;
            depth = d;
            cost = c;
        }
    }
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

        int[][] graph = new int[n][n];
        for (int[] flight : flights){
            graph[flight[0]][flight[1]] = flight[2];
        }

        Map<Integer, Integer> hash = new HashMap<>();
        PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> a.cost - b.cost);
        pq.offer(new Node(src, 0, 0));
        hash.put(0 * 1000 + src, 0);

        while (!pq.isEmpty()){
            System.out.println(pq.size());
            Node cur = pq.poll();

            if (cur.depth > K + 1 ) continue;

            if (cur.index == dst) return cur.cost;

            for (int nei = 0; nei < n; nei++){
                if (graph[cur.index][nei] > 0){
                    int newCost = cur.cost + graph[cur.index][nei];
                    if (newCost < hash.getOrDefault((cur.depth + 1) * 1000 + nei, Integer.MAX_VALUE)){
                        hash.put((cur.depth + 1) * 1000 + nei, newCost);
                        pq.offer(new Node(nei, cur.depth + 1, newCost));
                    }
                }
            }
        }

        return -1;
    }
}