题目描述

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1

样例

输入：[[0,1],[1,0]]

输出：2

输入：[[0,0,0],[1,1,0],[1,1,0]]

输出：4

算法1

(bfs)

从( 0， 0 )点开始进行bfs
将点放入queue中后，将对应的grid上的值置为1

C++ 代码

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {

        int n = grid.size();
        if( grid[ 0 ][ 0 ] || grid[ n - 1 ][ n - 1 ] ) return -1;
        int goal = -1;

        queue< pair< pair< int, int >, int > > q;

        q.push( { { 0, 0 }, 1 } );
        grid[ 0 ][ 0 ] = 1;

        while( !q.empty() )
        {
            auto now = q.front();
            q.pop();
            int x = now.first.first;
            int y = now.first.second;
            int val = now.second;

            if( x == n - 1 && y == n - 1 )
            {
                goal = val;
                break;
            }

            for( int i = -1; i <= 1; i ++ )
            for( int j = -1; j <= 1; j ++ )
            {
                if( i == 0 && j == 0 ) continue;
                int nx = x + i;
                int ny = y + j;
                if( nx < 0 || nx >= n || ny < 0 || ny >= n || grid[ nx ][ ny ] ) continue;
                q.push( { { nx, ny }, val + 1 } );
                grid[ nx ][ ny ] = 1;
            }
        }
        return goal;
    }
};