class Solution {
public:
    bool issafe(vector<vector<int>>& matrix, int i, int j) {
        return (i >= 0 && i < matrix.size() && j >= 0 && j < matrix[0].size() && matrix[i][j] == 0);
    }

    void solve(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& memo, int lencount, int& min_len) {
        if (i == matrix.size() - 1 && j == matrix[0].size() - 1) {
            min_len = min(min_len, lencount);
            return;
        }
        if (memo[i][j] != -1 && lencount >= memo[i][j]) {
            return;
        }
        memo[i][j] = lencount;

        vector<pair<int,int>> dir = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

        for (int k = 0; k < 8; k++) {
            int r = i + dir[k].first;
            int c = j + dir[k].second;

            if (issafe(matrix, r, c)) {
                solve(matrix, r, c, memo, lencount + 1, min_len);
            }
        }
    }

    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0] == 1 || grid[grid.size()-1][grid[0].size()-1] == 1) return -1;
        vector<vector<int>> memo(grid.size(), vector<int>(grid[0].size(), -1));
        int min_len = INT_MAX;
        solve(grid, 0, 0, memo, 1, min_len);
        if (min_len == INT_MAX) return -1;
        return min_len;
    }
};