【Leetcode】1091. Shortest Path in Binary Matrix（第141周周赛）（搜索+优先队列）

梦里梦外; 2022-01-13 11:23 182阅读 0赞

In an N by N square grid, each cell is either empty (0) or blocked (1).

A *clear path from top-left to bottom-right* has length `k` if and only if it is composed of cells `C_1, C_2, ..., C_k` such that:

*  Adjacent cells `C_i` and `C_{i+1}` are connected 8-directionally (ie., they are different and share an edge or corner)
 *  `C_1` is at location `(0, 0)` (ie. has value `grid[0][0]`)
 *  `C_k` is at location `(N-1, N-1)` (ie. has value `grid[N-1][N-1]`)
 *  If `C_i` is located at `(r, c)`, then `grid[r][c]` is empty (ie. `grid[r][c] == 0`).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

**Example 1:**

Input: [[0,1],[1,0]]
    Output: 2

**Example 2:**

Input: [[0,0,0],[1,1,0],[1,1,0]]
    Output: 4

**Note:**

1.  `1 <= grid.length == grid[0].length <= 100`
2.  `grid[i][j]` is `0` or `1`

题目大意：

很典型的搜索，但是其中包含了大量的无关路径，需要剪枝，使用优先队列保证每次取到了都是最小的代价。

struct node{
            int x,y,step;
    };
    bool operator < (node a,node b){
        return a.step>b.step;
    }
    class Solution {
    private:
        bool maps[110][110];
        int xx[8] = {1,1,0,-1,0,1,-1,-1};
        int yy[8] = {0,1,1,0,-1,-1,1,-1};
        
        bool valid(int x, int y, vector<vector<int> >& grid){
            if(x>=0&&x<grid.size()&&y>=0&&y<grid.size()&&grid[x][y]!=1&&maps[x][y]==false) return true;
            return false;
        }
        int helper(vector<vector<int> >& grid){
            priority_queue<node> q;
            node start={0,0,0};
            q.push(start);
            while(!q.empty()){
                node s = q.top();
                q.pop();
                if(s.x==grid.size()-1 && s.y==grid.size()-1) return s.step+1;
                for(int i = 0;i<8;i++){
                    int cor_x, cor_y;
                    cor_x = s.x + xx[i];
                    cor_y = s.y + yy[i];
                    if(valid(cor_x, cor_y, grid)){
                        maps[cor_x][cor_y] = true;
                        node next={cor_x,cor_y,s.step+1};
    				    q.push(next);
                    }
                }
            }
            
            return -1;
        }
    public:
        int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
            if(grid[0][0]==1 || grid[grid.size()-1][grid.size()-1]==1)   return -1;
            memset(maps, false, sizeof(maps));
            maps[0][0] = true;
            return helper(grid);
        }
    };