[leetcode]-1293 Shortest Path in a Grid with Obstacles Elimination

小灰灰 2023-06-29 02:21 42阅读 0赞

题目：

Given a `m * n` grid, where each cell is either `0` (empty) or `1` (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner `(0, 0)` to the lower right corner `(m-1, n-1)` given that you can eliminate **at most** `k` obstacles. If it is not possible to find such walk return -1.

思路：

BFS (Breadth First Search) 宽度优先搜索，使用队列（queue）来实现：首先把根节点放到队列中；每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾；并把这个元素记为它下一级元素的前驱；找到所要找的元素时结束程序；如果遍历整个树还没有找到，结束程序。

本题中将宽度视为所走的步数step：

1）开始时将(0,0)放入队列中；

2）每次从队列的头部取出一个格子，查看所有它能走到的所有格子（上、下、左、右），加入到队列的末尾；

3）当取出的元素为(m-1,n-1)时，记录步数并更新最小值；

4）直到队列为空。

本题重点：

判断格子是否被访问过，应该用x坐标、y坐标、剩余obstacle数目三个维度，而不是仅仅x坐标和y坐标两个维度。

代码：

import java.util.LinkedList;
    import java.util.Queue;
    
    class ShortestPath{
        class Node{
            public int x, y, step, obstacle;
            public Node(int x, int y, int step, int obstacle){
                this.x = x;
                this.y = y;
                this.step = step;
                this.obstacle = obstacle;
            }
        }
    
        public int shortestPath(int[][] grid, int k) {
            //the min steps when arrive at (m-1,n-1)
            int count = -1;
            Queue<Node> list = new LinkedList();
            //boolean array to check when the grid is visited or not
            boolean[][][] visited = new boolean[grid.length][grid[0].length][k+1];
            for(int i =0; i < grid.length; ++i)
                for(int j = 0; j < grid[0].length; ++j)
                    for(int h = 0; h < k+1; ++h)
                        visited[i][j][h] = false;
            //add (0,0) to the head of the queue
            list.add(new Node(0,0, 0,k-grid[0][0]));
            visited[0][0][k] = true;
            while(!list.isEmpty()){
                Node tmp = list.poll();
                //when arrive at (m-1,n-1)
                if(tmp.x == grid.length-1 && tmp.y == grid[0].length-1 
                        && tmp.obstacle >= 0){
                    if(count == -1){
                        count = tmp.step;
                        System.out.println("arrive :" + count);
                    }else if(tmp.step <= count){
                        count = tmp.step;
                        System.out.println("arrive :" + count);
                    }
                }
                //four cases: left, right, up, down
                if(tmp.x-1 >= 0){
                    int newk = tmp.obstacle-grid[tmp.x-1][tmp.y];
                    if(newk >= 0 && visited[tmp.x-1][tmp.y][newk] == false) {
                        list.add(new Node(tmp.x - 1, tmp.y, tmp.step + 1, newk));
                        visited[tmp.x - 1][tmp.y][newk] = true;
                    }
                }
                if(tmp.x +1 < grid.length ){
                    int newk = tmp.obstacle-grid[tmp.x+1][tmp.y];
                    if(newk >= 0 && visited[tmp.x+1][tmp.y][newk] == false) {
                        list.add(new Node(tmp.x+1, tmp.y, tmp.step + 1, newk));
                        visited[tmp.x+1][tmp.y][newk] = true;
                    }
                }
                if(tmp.y-1 >= 0){
                    int newk = tmp.obstacle-grid[tmp.x][tmp.y-1];
                    if(newk >= 0 && visited[tmp.x][tmp.y-1][newk] == false) {
                        list.add(new Node(tmp.x,tmp.y-1, tmp.step + 1, newk));
                        visited[tmp.x][tmp.y-1][newk] = true;
                    }
                }
                if(tmp.y + 1 < grid[0].length){
                    int newk = tmp.obstacle-grid[tmp.x][tmp.y+1];
                    if(newk >= 0 && visited[tmp.x][tmp.y+1][newk] == false) {
                        list.add(new Node(tmp.x, tmp.y+1, tmp.step + 1, newk));
                        visited[tmp.x][tmp.y+1][newk] = true;
                    }
                }
            }
            return count;
        }
    
    }