You are given a binary matrix grid of size m $\times$ n.

From any cell $(r, c)$, you are permitted to move to $(r + 1, c)$ or $(r, c + 1)$ as long as the destination cell contains the value $1$.

The matrix is disconnected if there is no valid path from the top left cell $(0, 0)$ to the bottom right cell (m $- 1$, n $- 1$).

You are allowed to flip the value of at most one cell from $1$ to $0$, excluding the cells $(0, 0)$ and (m $- 1$, n $- 1$).

Return true if it is possible to make the matrix disconnected after flipping at most one cell, or false otherwise.

Note: Flipping at most one cell means you can choose to flip $0$ or $1$ cell. A path is valid only if every cell visited has a value of $1$.

Constraints:

• m $==$ grid.length

• n $==$ grid[i].length

• $1 \leq$ m, n $\leq 1000$

• $1 \leq$ m $\times$ n $\leq 10^5$

• grid[i][j] is either $0$ or $1$.

• grid[0][0] $==$ grid[m - 1][n - 1] $== 1$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.