题目描述
给你一个下标从$0$开始的$m \times 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$。
示例$1$:
输入:grid = [[1,1,1],[1,0,0],[1,1,1]]
输出:true
解释:按照上图所示我们翻转蓝色格子里的值,翻转后从 (0, 0) 到 (2, 2) 没有路径。
示例$2$:
输入:grid = [[1,1,1],[1,0,1],[1,1,1]]
输出:false
解释:无法翻转至多一个格子,使 (0, 0) 到 (2, 2) 没有路径。
提示:
- $m = grid.length$
- $n = grid[i].length$
- $1 \leq m, n \leq 1000$
- $1 \leq m \times n \leq 10^5$
- $grid[0][0] = grid[m - 1][n - 1] = 1$
算法1
$BFS$+后缀和
这个题虽然标的中等,但是很麻烦,写了一堆代码。从$(m-1,n-1)$位置开始$BFS$,每次只能往上或往左走,把能到的位置标记上$1$记录在$vistied1$矩阵中;从$(0,0)$位置开始$BFS$,每次只能往下或往右走,把能到的位置标记上$1$记录在$visited2$矩阵当中。如果$visited1[x][y]=1$,表示从$(x,y)$能够到$(m-1,n-1)$;如果$visited2[x][y]=1$表示从$(0,0)$可以到$(x,y)$。
接下来分析题目要求的这个“桥连点”的性质,我们可以发现,如果$(x,y)$是这个关键的桥连点,那么肯定满足:
- $visited1[x][y]=1$;
- 并且由于从$(0,0)$出发只能往下或往右走,在$visited1$矩阵中,$(x,y)$的右边要么就没有$1$,要么这个$1$的上邻居肯定不是$1$,也就是说如果存在$z \gt y$满足$visited2[x][z]=1$,它的正上方肯定不是$1$,这说明$(x,z)$只能通过$(x,y)$从左边过来,不能从上面过来。
- 同理,$(x,y)$的下面要么就没有$1$,要么这个$1$的左邻居肯定不是$1$。也就是说,如果存在$z \gt x$满足$visited1[z][y]=1$,那么无法从左边到$(z,y)$,只能通过$(x,y)$从上面过来。
因此我们可以预处理出$left$和$down$数组,$left[x][y]$表示$visited1[x][y-1]$是不是$1$,$up[x][y]$表示$visited1[x-1][y]$是不是$1$。然后预处理出$left$在列方向上的后缀和,$up$在行方向上的后缀和,这样就能快速求得某个位置$(x,y)$的右边和下面有没有能够不通过自己到达$(m-1,n-1)$的点。
最后遍历所有的位置,根据上面的要求判断就能够找到这个“关键”位置。
复杂度分析
两次$BFS$时间复杂度$O(mn)$,其他都是双重循环遍历矩阵的操作,时间复杂度也在$O(mn)$的级别,因此算法的整体时间复杂度也为$O(mn)$。开辟了有限几个$O(mn)$级别的辅助数组,因此算法的额外空间复杂度为$O(mn)$。
C++ 代码
int dx1[2] = {0, -1}, dy1[2] = {-1, 0}, dx2[2] = {0, 1}, dy2[2] = {1, 0};
class Solution {
public:
bool isPossibleToCutPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> visited1(m, vector<int>(n)), visited2(m, vector<int>(n)), right(m, vector<int>(n)), down(m, vector<int>(n));
vector<vector<bool>> st1(m, vector<bool>(n));
queue<pair<int, int>> q;
// visited1[x][y]=1表示(x,y)可以到(m-1,n-1)
q.push({m - 1, n - 1});
st1[m - 1][n - 1] = true;
while(!q.empty()) {
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
visited1[x][y] = 1;
for(int i = 0; i < 2; i++) {
int nx = x + dx1[i], ny = y + dy1[i];
if(nx >= 0 && ny >= 0 && grid[nx][ny] && !st1[nx][ny]) {
q.push({nx, ny});
st1[nx][ny] = true;
}
}
}
if(!visited1[0][0]) return true; // 本来就过不去
// visited2[x][y]=1表示(0,0)可以到(x,y)
vector<vector<bool>> st2(m, vector<bool>(n));
q.push({0, 0});
st2[0][0] = true;
while(!q.empty()) {
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
visited2[x][y] = 1;
for(int i = 0; i < 2; i++) {
int nx = x + dx2[i], ny = y + dy2[i];
if(nx < m && ny < n && grid[nx][ny] && !st2[nx][ny]) {
q.push({nx, ny});
st2[nx][ny] = true;
}
}
}
vector<vector<int>> left(m, vector<int>(n)), up(m, vector<int>(n));
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(visited1[i][j]) {
left[i][j] = visited2[i][j - 1];
up[i][j] = visited2[i - 1][j];
}
}
}
for(int i = 0; i < m; i++) {
for(int j = n - 1; j >= 0; j--) {
up[i][j] += j < n - 1? up[i][j + 1]: 0;
}
}
for(int j = 0; j < n; j++) {
for(int i = m - 1; i >= 0; i--) {
left[i][j] += i < m - 1? left[i + 1][j]: 0;
}
}
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;
if(visited1[i][j]) {
int down = i < m - 1? left[i + 1][j]: 0;
int right = j < n - 1? up[i][j + 1]: 0;
if(down == 0 && right == 0) return true;
}
}
}
return false;
}
};