---
tags: leetcode
---

# [1091. Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/)
---
# My Solution
## The Key Idea for Solving This Coding Question
BFS
## C++ Code

#define WHITE (0)
#define GRAY (1)
#define BLACK (2)

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
        if (grid[0][0] != 0) {
            return -1;
        }

        int n = grid.size();
        vector<vector<int>> state(n, vector<int>(n, WHITE));

         return bfs(grid, state, n);
    }

private:
    int bfs(vector<vector<int>> &grid, vector<vector<int>> &state, int n) {
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
        queue<cell> q;
        int shortestLen = 1;

        q.push(cell(0, 0));
        state[0][0] = GRAY;
        while (!q.empty()) {
            int qLen = q.size();
            for (int i = 0; i < qLen; ++i) {
                cell curr = q.front();
                q.pop();

                if (curr.r == n -1 && curr.c == n - 1) {
                     return shortestLen;
                }

                for (auto &dir : dirs) {
                    int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                    if (nextR < 0 || n <= nextR || nextC < 0 || n <= nextC ||
                           state[nextR][nextC] != WHITE || grid[nextR][nextC] != 0) {
                        continue;
                    }
                    q.push(cell(nextR, nextC));
                    state[nextR][nextC] = GRAY;
                }
                 state[curr.r][curr.c] = BLACK;
            }
            ++shortestLen;
        }

        return -1;
    }
};

## Time Complexity
$O(n^{2})$
$n$ is the size of the square matrix referred by `grid`.
## Space Complexity
$O(n^{2})$
# Miscellaneous
<!--
# Test Cases

[[0,1],[1,0]]

[[0,0,0],[1,1,0],[1,1,0]]

[[1,0,0],[1,1,0],[1,1,0]]

* Time Limit Exceeded

[[0,1,1,1,1,1,1,1],[0,1,1,0,0,0,0,0],[0,1,0,1,1,1,1,0],[0,1,0,1,1,1,1,0],[0,1,1,0,0,1,1,0],[0,1,1,1,1,0,1,0],[0,0,0,0,0,1,1,0],[1,1,1,1,1,1,1,0]]

* Time Limit Exceeded
https://leetcode.com/submissions/detail/746914880/testcase/
* Wrong Answer

[[0,0,1,0],[1,0,1,0],[1,1,0,1],[0,0,0,0]]

* Wrong Answer

[[0,0,0,0,1],[1,0,0,0,0],[0,1,0,1,0],[0,0,0,1,1],[0,0,0,1,0]]

-->