【割点 C++BFS】2556. 二进制矩阵中翻转最多一次使路径不连通

本文涉及知识点

割点图论知识汇总
C++BFS算法

LeetCode2556. 二进制矩阵中翻转最多一次使路径不连通

给你一个下标从 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 。
示例 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 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[0][0] == grid[m - 1][n - 1] == 1

割点

如果有封装类，直接使用割点更简单。

BFS

vector<unorder_set>> leve[i] 记录i步可以到达的坐标,i $\in$ [0,m-1+n-1]
如果leve.size()小于等于2，只经过起点和终点，所以一定能够连通。
否则返回 cout(leve.begin()+1,leve.end()-1,1) > 0 。
由于只能向右或下走，所以不会有环。只需要处理，同一步的重复。

错误

必须排除无法到达终点的点。如：
在这里插入图片描述
图中的数字表示多少步到达此格。绿色数字表示能到达终点，蓝色数字表示无法到达终点。叉叉表示grid[r][c]为0而无法进入。
canVis记录各点能否到达终点，不能到达终点的点忽略。

代码

核心代码

class Solution {
public:bool isPossibleToCutPath(vector<vector<int>>& grid) {const int R = grid.size();const int C = grid[0].size();vector<vector<bool>> canVis(R, vector<bool>(C));canVis.back().back() = true;for (int r = R - 1; r >= 0; r--) {for (int c = C - 1; c >= 0; c--) {if ((r + 1 < R) && canVis[r + 1][c]&& grid[r + 1][c]) {canVis[r][c] = true ;}if ((c + 1 < C) && canVis[r][c + 1]&& grid[r][c + 1]) {canVis[r][c] = true;}}}const int m = R - 1 + C - 1;vector<set<pair<int, int>>> leves(m + 1);leves[0].emplace(0, 0);for (int i = 0; i < m; i++) {for (auto [r, c] : leves[i]) {if ((r + 1 < R) && grid[r + 1][c] && canVis[r + 1][c]) {leves[i + 1].emplace(r + 1, c);}if ((c + 1 < C) && grid[r][c + 1] && canVis[r][c + 1]) {leves[i + 1].emplace(r , c + 1);}}}if (leves.back().empty()) { return true; }for (int i = 1; i < m; i++) {if (1 == leves[i].size()) { return true; }}return false;}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1,  double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<vector<int>> grid;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){grid = { {1,1,1},{1,0,0},{1,1,1} };auto res = Solution().isPossibleToCutPath(grid);AssertEx(true, res);}TEST_METHOD(TestMethod01){grid = { {1,1,1},{1,0,1},{1,1,1} };auto res = Solution().isPossibleToCutPath(grid);AssertEx(false, res);}TEST_METHOD(TestMethod02){grid = { {1,1,1},{1,0,0},{1,1,1},{1,1,1} };auto res = Solution().isPossibleToCutPath(grid);AssertEx(true, res);}};
}