【割点 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 public: bool isPossibleToCutPath(vector const int R = grid.size(); const int C = grid[0].size(); vector for (int c = C - 1; c = 0; c--) { if ((r + 1

单元测试

template
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)