本文涉及知识点

割点 图论知识汇总

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记录各点能否到达终点，不能到达终点的点忽略。

代码

核心代码

<code>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);

}

};

}