题目描述：
给你一个下标从 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\le m, n\le 10^3, 1\le m \times n \le 10^5$
题解：
如果存在关键节点，那么可以找出中间轮廓的上下边界，如果上下边界存在交集说明存在关键节点，否则不存在关键节点。如果找出上下边界，找下边界的话，可以先往下走，再向右走（只有向下走不下去时才向右走）；找上边界时，先往右走，走不下去再向下走。
实现的时候可以先找一个边界，然后把走过的格子修改为 $0$ ，然后看有没有 $(0,0)$ 到 $(m,n)$ 的路径。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
bool isPossibleToCutPath(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
unordered_set<int> up;
function<bool(int, int)> dfs = [&](int x, int y)
{
if (x == n - 1 && y == m - 1)
return true;
grid[x][y] = 0;
bool ret1, ret2;
if (x + 1 < n && grid[x + 1][y] == 1)
ret1 = dfs(x + 1, y);
if (!ret1 && y + 1 <= m && grid[x][y + 1] == 1)
ret2 = dfs(x, y + 1);
return ret1 || ret2;
};
if (!dfs(0, 0))
return true;
return !dfs(0, 0);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
bool isPossibleToCutPath(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
unordered_set<int> up;
function<bool(int, int)> dfs = [&](int x, int y)
{
if (x == n - 1 && y == m - 1)
return true;
grid[x][y] = 0;
bool ret1, ret2;
return x + 1 < n && grid[x + 1][y] == 1 && dfs(x + 1, y) || y + 1 <= m && grid[x][y + 1] == 1 && dfs(x, y + 1);
};
return !dfs(0, 0) || !dfs(0, 0);
}
};
|