2556. Disconnect Path in a Binary Matrix by at Most One Flip

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1).

You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1).

Return true if it is possible to make the matrix disconnect or false otherwise.

Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

class Solution {
    vector<vector<int>> bfs(vector<vector<int>>& A, int sy, int sx, vector<int> dy, vector<int> dx) {
        int n = A.size(), m = A[0].size();
        vector<vector<int>> res(n,vector<int>(m));
        queue<pair<int,int>> q;
        auto push = [&](int y, int x) {
            if(0 <= y and y < n and 0 <= x and x < m and A[y][x] and !res[y][x]) {
                res[y][x] = true;
                q.push({y,x});
            }
        };
        push(sy,sx);
        while(q.size()) {
            auto [y,x] = q.front(); q.pop();
            for(int i = 0; i < 2; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                push(ny,nx);
            }
        }
        return res;
    }
public:
    bool isPossibleToCutPath(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();
        auto mat1 = bfs(A,n-1,m-1,{-1,0},{0,-1});
        auto mat2 = bfs(A,0,0,{1,0},{0,1});
        vector<int> dp(n*m);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int now = mat1[i][j] and mat2[i][j];
                dp[i+j] += now;
            }
        }
        for(int i = 1; i < (n - 1 + m - 1); i++) if(dp[i] <= 1) return true;
        return false;
    }
};