给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。 你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。 如果可以使矩阵不连通，请你返回 true ，否则返回 false 。 注意 ，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。 输入：grid = [[1,1,1],[1,0,0],[1,1,1]] 输出：true,要求有解题思路，解题思路。解题思路包括需要包含: 状态定义 初始状态 状态转移⽅程

解题思路：

首先，我们需要判断原始矩阵是否连通。可以使用广度优先搜索或深度优先搜索来实现。

接着，我们需要考虑翻转一个格子后矩阵是否连通。为此，我们可以枚举每个位置，将该位置的值翻转，然后再次判断矩阵是否连通。如果矩阵不连通，则返回 true，否则继续枚举下一个位置。如果所有位置都尝试过了，矩阵仍然连通，则返回 false。

状态定义：

我们可以使用一个二维数组 visited 记录每个格子是否被访问过。

初始状态：

visited 数组中所有元素均为 false。

状态转移方程：

假设当前搜索到了坐标为 (i, j) 的格子，我们可以向下或向右走。如果向下走，坐标变成了 (i+1, j)，如果向右走，坐标变成了 (i, j+1)。我们需要判断这两个格子是否越界，是否被访问过，以及其值是否为 1。如果满足条件，我们将该格子标记为已访问，并将其加入队列中。

代码实现：

使用广度优先搜索实现：

class Solution {
public:
    bool isNotConnected(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({0, 0});
        visited[0][0] = true;
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            if (i == m - 1 && j == n - 1) {
                return false;
            }
            if (i + 1 < m && grid[i + 1][j] == 1 && !visited[i + 1][j]) {
                q.push({i + 1, j});
                visited[i + 1][j] = true;
            }
            if (j + 1 < n && grid[i][j + 1] == 1 && !visited[i][j + 1]) {
                q.push({i, j + 1});
                visited[i][j + 1] = true;
            }
        }
        return true;
    }

    bool canTurnOffOneCell(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0 || i == m - 1 && j == n - 1) {
                    continue;
                }
                grid[i][j] = 1 - grid[i][j]; // 翻转格子
                if (isNotConnected(grid)) { // 判断是否不连通
                    return true;
                }
                grid[i][j] = 1 - grid[i][j]; // 恢复格子原来的值
            }
        }
        return false;
    }

    bool isEscapePossible(vector<vector<int>>& blocked) {
        vector<vector<int>> grid(1e6, vector<int>(1e6, 1));
        int min_x = 1e6, min_y = 1e6, max_x = 0, max_y = 0;
        for (auto& b : blocked) {
            int x = b[0], y = b[1];
            grid[x][y] = 0;
            min_x = min(min_x, x);
            min_y = min(min_y, y);
            max_x = max(max_x, x);
            max_y = max(max_y, y);
        }
        int m = max_x - min_x + 1, n = max_y - min_y + 1;
        vector<vector<int>> newGrid(m, vector<int>(n, 0));
        for (auto& b : blocked) {
            int x = b[0] - min_x, y = b[1] - min_y;
            newGrid[x][y] = 1;
        }
        return !isNotConnected(newGrid) || canTurnOffOneCell(newGrid);
    }
};

时间复杂度：翻转格子的数量为 O(mn)，每次判断是否不连通的时间复杂度为 O(mn)，因此总时间复杂度为 O(m^2 n^2)。

空间复杂度：visited 数组使用 O(mn) 的额外空间，queue 使用 O(min(m, n)) 的额外空间，因此总空间复杂度为 O(mn)。