1091. Shortest Path in Binary Matrix

• Link: https://leetcode.com/problems/shortest-path-in-binary-matrix/

Question

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0|0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0|0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0|1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

Approach 1: BFS

Intuition

• Directions array as neighbors
• BFS maintaining current distance

Algorithm

Code

class Solution {
public:
    vector<pair<int, int>> directions = {
        {-1, -1},
        {-1, 0},
        {-1, 1},
        {0, -1},
        {0, 1},
        {1, -1},
        {1, 0},
        {1, 1}
    };

    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> visited(rows, vector<int>(cols, 0));
        // {{row, col}, dist}
        queue<pair<pair<int, int>,int>> q;     
        if (grid[0][0] == 0) {
            q.push({{0, 0}, 1});
            visited[0][0] = 1;
        }

        while(!q.empty()) {
            int r = q.front().first.first;
            int c = q.front().first.second;
            int currDistance = q.front().second;
            q.pop();

            if (r == rows - 1 && c == cols - 1) {
                return currDistance;
            }

            for (auto direction: directions) {
                int nr = r + direction.first;
                int nc = c + direction.second;

                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 0 || visited[nr][nc]) continue;


                q.push({{nr, nc}, currDistance + 1});
                visited[nr][nc] = 1;
            }
        }

        return -1;
    }
};

Complexity Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$