@1091. Shortest Path in Binary Matrix

• 方法1: bfs
• 方法2: dfs， TLE

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

方法1: bfs

思路：

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0] || grid.back().back()) return -1;
        int m = grid.size(), n = grid[0].size(), level = 1;
        queue<vector<int>> q;
        q.push({0, 0});
        while (!q.empty()) {
            int sz = q.size();
            level++;
            for (int k = 0; k < sz; k++) {
                auto top = q.front();
                q.pop()@;
                
                for (int i = -1; i <= 1; i++) {
                    for (int j = -1; j <= 1; j++) {
                        if (!i && !j) continue;
                        int x = top[0] + i;
                        int y = top[1] + j;
                        
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] > 0) continue;
                        if (x == m - 1 && y == n - 1) return level;
                        grid[x][y] = 2;
                        q.push({x, y});
                    }
                }
            }
            
        }
        return -1;
    }
};

方法2: dfs， TLE

注意这道题，dfs是打死也过不了的，目测过了的人全都是用的bfs。

class Solution {
private:
    int mn;
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0] || grid.back().back()) return -1;
        int N = grid.size();
        mn = N * N + 1;
        dfs(grid, N, 1, 0, 0);
        if (mn != N * N + 1) return mn;
        return -1;
    }
    
    void dfs(vector<vector<int>> & grid, int N, int current, int i, int j) {
        if (i == N - 1 && j == N - 1) {
            if (current < mn) mn = current;
            return;
        }
        grid[i][j] = 2;
        for (int s = 1; s >= -1; s--) {
            for (int t = 1; t >= -1; t--) {
                if (s == 0 && t == 0) continue;
                int x = i + s;
                int y = j + t;
                if (x < 0 || x >= N || y < 0 || y >= N || current > mn || max(N - x, N - y) >= mn || grid[x][y] > 0) continue; 
                dfs(grid, N, current + 1, x, y);
            }
        }
        grid[i][j] = 0;
        return;
    }
};