1293. Shortest Path in a Grid with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

class Solution {
    public int[][] DIR = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    private class Node {
        int i;
        int j;
        // with k elimination left
        int k;
        public Node(int i, int j, int k) {
            this.i = i;
            this.j = j;
            this.k = k;
        }
        public String toString() {
            // k是必须要的，同一个位置用了不同次elimination是不一样的
            return i + " " + j + " " + k;
        }
    }
    public int shortestPath(int[][] grid, int k) {
        Queue<Node> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        int steps = 0;
        int m = grid.length;
        int n = grid[0].length;
        queue.offer(new Node(0, 0, k));
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                Node node = queue.poll();
                if (node.i == m - 1 && node.j == n - 1 && node.k >= 0) {
                    return steps;
                }
                if (visited.contains(node.toString())) {
                    continue;
                }
                visited.add(node.toString());
                for (int[] dir : DIR) {
                    int x = node.i + dir[0];
                    int y = node.j + dir[1];
                    
                    if (x >= 0 && y >= 0 && x < m && y < n) {
                        if (grid[x][y] == 1 && node.k > 0) {
                            queue.offer(new Node(x, y, node.k - 1));
                        } else if (grid[x][y] == 0) {
                            queue.offer(new Node(x, y, node.k));
                        }
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

其实不算很难？注释那里要注意一下