1293. Shortest Path in a Grid with Obstacles Elimination

add one more dimension in visited

[x][y]k+1]: 記錄在某座標, 第三維紀錄 使用的消除次數 0~k （boolean

so

然後分有障礙的座標和沒障礙的座標去處理
if (grid[x][y] == 1)
else

再遇到有障礙的座標時, 這樣代表用完了

if (k == obs || visited[x][y][k+1])

k == obs, 代表 消除次數用到 k 次了, 不能再用
visited[x][y][k+1] 代表在這座標上 消除次數的狀態（true, 代表 k次消除次數在這座標用了
in next queue poll, we can get from previous xy 座標和 用了幾次消除次數（k)

T: O(mnk) , mn is the be the number of cells in the grid, and K be the quota to eliminate obstacles.

S: O(mnk)

class Solution {
    private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    public int shortestPath(int[][] grid, int obs) {
        int m = grid.length;
        int n = grid[0].length;
        
        // 注意 visited 狀態可以這樣寫, 多一個 "使用的消除障礙數"
        boolean visited[][][] = new boolean[m][n][obs+1]; // obs: 0~obs => obs+1
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0,0,0});
        visited[0][0][0] = true;
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int currX = curr[0];
                int currY = curr[1];
                int k = curr[2];

                // 寫在外面的優點是, 當只有一個 data 時, 這邊是可以返回的, 寫在內層無法, 要特別處理
                if (currX == m - 1 && currY == n - 1) { 
                    return steps;
                }
                for (int dir[] : dirs) {
                    int x = currX + dir[0];
                    int y = currY + dir[1];

                    if (!isInArea(grid, x, y)) {
                        continue;
                    }

                    if (grid[x][y] == 1) { // 如果是障礙,  需要用消除障礙, 才能繼續加到 queue bfs
                        if (k == obs || visited[x][y][k+1]) { // k == obs, 已經用完消除障礙的
                            continue;
                        }
                        queue.offer(new int[]{x, y, k+1}); // 消除障礙數目+1
                        visited[x][y][k+1] = true;
                        
                    } else { // 非障礙, 正常處理
                        if (visited[x][y][k]) {
                            continue;
                        }
                        queue.offer(new int[]{x, y, k});
                        visited[x][y][k] = true;
                    }
                }
            }
            steps++;
        }
        return -1;
    }
    
    private boolean isInArea(int[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}

/*

T: O(mnk)
S: O(mnk)

define
visited[i][j][k]

if (next 4 dir + (i,j)) == 1)

if k == K continue;
visited[new i][new j][k+1]

if (next 4 dir + (i,j)) == 0)

visited[new i][new j][k]

*/

simpler version

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][][] visited = new boolean[m][n][k+1];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 0});
        visited[0][0][0] = true;
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int curX = cur[0];
                int curY = cur[1];
                int curObs = cur[2];
                if (curX == m - 1 && curY == n - 1) {
                    return steps;
                }
                
                for (int[] dir : DIRS) {
                    int x = dir[0] + curX;
                    int y = dir[1] + curY;
                    
                    // alert!! this curObs must assign to a new variable(obs), 
                    // or it will be wrong!!!
                    int obs = curObs; 
                    if (!isValid(grid, x, y)) {
                        continue;
                    }
                    if (grid[x][y] == 1) {
                        obs++;
                    }
                    if (obs > k || visited[x][y][obs]) {
                        continue;
                    }
                    queue.offer(new int[] {x, y, obs});
                    visited[x][y][obs] = true;
                }
            }
            steps++;
        }
        return -1;
    }
    private boolean isValid(int[][] grid, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

print with path

class Solution {
    private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    private static final String[] DIRSTR = {"d", "u", "r", "l"}; // row col base
    class Data {
        int x;
        int y;
        int obs;
        String path;
        
        Data (int x, int y, int obs, String path) {
            this.x = x;
            this.y = y;
            this.obs = obs;
            this.path = path;
        }
    }
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][][] visited = new boolean[m][n][k+1]; // k+1 !
        Queue<Data> queue = new LinkedList<>();
        queue.offer(new Data(0 , 0, 0, ""));
        visited[0][0][0] = true;
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                Data cur = queue.poll();
                int curX = cur.x;
                int curY = cur.y;
                int curObs = cur.obs;
                String curPath = cur.path;

                if (curX == m - 1 && curY == n - 1) {
                    System.out.println("final path:" + curPath);
                    return steps;
                }
                for (int i = 0; i < 4; i++) {
                    int x = curX + DIRS[i][0];
                    int y = curY + DIRS[i][1];
                    int obs = curObs;
                    String path = curPath + DIRSTR[i];
                    
                    if (!isValid(m, n, x, y)) {
                        continue;
                    }
                    if (grid[x][y] == 1) {
                        obs++;
                    }
                    if (obs > k || visited[x][y][obs]) {
                        continue;
                    }
                    queue.offer(new Data(x , y, obs, path));
                    visited[x][y][obs] = true;
                }
            }
            steps++;
        }
        return -1;
    }
    private boolean isValid(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

/*
weight is 1
BFS
you can eliminate at most k obstacles => use one more dim to record eliminatation times <= k

Queue<int[]> => int[x][y][k]

start from 0,0 end to m-1, n-1

T: O(mnk)
S: O(mnk)
*/

shorter version

class Solution {
    private static final int[][] DIRS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][][] visited = new boolean[m][n][k+1]; // 0~k obs
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0 , 0, 0});
        visited[0][0][0] = true;
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                
                if (cur[0] == m-1 && cur[1] == n - 1) {
                    return steps;
                }
                for (int[] dir : DIRS) {
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];
                    int toolUsedCount = cur[2];
                    if (!inArea(grid, x, y)) {
                        continue;
                    }
                    if (grid[x][y] == 1) { // if is obstacle, use tool to eliminate
                        toolUsedCount++;
                    }
                    if (toolUsedCount > k || visited[x][y][toolUsedCount]) {
                        continue;
                    }
                    queue.offer(new int[]{x, y, toolUsedCount});
                    visited[x][y][toolUsedCount] = true;
                }
            }
            steps++;
        }
        return -1;
    }
    private boolean inArea(int[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
}

/*
010
000
010

*/

new version

```java
class Solution {
    private int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    class Step {
        int x;
        int y;
        int level;
        int removeCount;
        Step(int x, int y, int level, int removeCount) {
            this.x = x;
            this.y = y;
            this.level = level;
            this.removeCount = removeCount;
        }
    }
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(0, 0, 0, 0));
        boolean[][][] visited = new boolean[m][n][k+1];

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            if (!inArea(grid, cur.x, cur.y) || visited[cur.x][cur.y][cur.removeCount]) {
                continue;
            }

            if (cur.x == m-1 && cur.y == n-1) {
                return cur.level;
            }
            visited[cur.x][cur.y][cur.removeCount] = true;

            for (int[] dir : DIRECTIONS) {
                int x = cur.x + dir[0];
                int y = cur.y + dir[1];
                int count = cur.removeCount;

                if (inArea(grid, x, y) && grid[x][y] == 1) {
                    count++;
                }
                if (count > k) {
                    continue;
                }
                queue.offer(new Step(x, y, cur.level+1, count));
            }
        }
        return -1;
    }
    private boolean inArea(int[][] grid, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}
```

More consistent way

or ...still check count first... all good

```java
class Solution {
    private static final int[][] DIRECTIONS = {{1,0}, {0, 1}, {-1,0}, {0, -1}};
    class Step {
        int x;
        int y;
        int level;
        int removedObstacles;
        Step(int x, int y, int level, int removedObstacles) {
            this.x = x;
            this.y = y;
            this.level = level;
            this.removedObstacles = removedObstacles;
        }
    }
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(0, 0, 0, 0));

        boolean[][][] visited = new boolean[m][n][k+1];

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            // more consistent way
            if (!inArea(grid, cur.x, cur.y) || cur.removedObstacles > k || visited[cur.x][cur.y][cur.removedObstacles]) {
                continue;
            }
            visited[cur.x][cur.y][cur.removedObstacles] = true;
            if (cur.x == m - 1 && cur.y == n-1) {
                return cur.level;
            }
            for (int[] dir : DIRECTIONS) {
                int nextX = cur.x + dir[0];
                int nextY = cur.y + dir[1];
                int count = cur.removedObstacles;
                if (inArea(grid, nextX, nextY) && grid[nextX][nextY] == 1) {
                    count++;
                }
                queue.offer(new Step(nextX, nextY, cur.level + 1, count));
            }
        }
        return -1;
    }
    private boolean inArea(int[][] grid, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        return x >= 0 && x < m && y >=0 && y < n;
    }
}
```