[leetcode]-1293 Shortest Path in a Grid with Obstacles Elimination-蒲公英云

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

小灰灰 2023-06-29 02:21 72阅读 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;
    }
}