检查网格中编号为 1 到 K 的单元格在移除至少一个阻塞单元格后是否可以连接
在此问题中，我们将检查是否可以通过解除任何单个单元格的阻塞来连接所有 K 个单元格。
为了解决这个问题，我们将所有连接的 K 视为一个岛。如果任何单个阻塞单元格可以连接矩阵的所有岛，则只能连接矩阵的所有 K 个单元格。因此，如果矩阵包含超过 4 个岛，则无法连接所有单元格。
问题陈述
我们给出了一个大小为 n*m 的 mat[] 矩阵。我们还给出了一个正整数 K。矩阵在某些单元格中包含 0 和 -1。此外，矩阵的 K 个单元格包含从 1 到 K 的值。这里，0 表示未阻塞的单元格，-1 表示阻塞的单元格。我们需要检查是否可以通过解除一个被阻塞的单元格的阻塞来连接所有 K 个单元格。
注意− 我们只能在水平和垂直方向上连接单元格。
示例
输入
mat = {{0, 2, 5, 0}, K = 6, N = 4, M = 4
{-1, 6, -1, 3},
{-1, -1, 4, -1},
{0, -1, 1, -1}};
输出
Yes
解释
如果我们解除 mat[1][2] 单元格的阻塞，我们就可以连接所有 K 个单元格。我们可以通过包含 0 的单元格连接任意两个单元格，因为它是一个未阻塞的单元格。
输入
mat = {{1, -1, 2, 0}, K = 4, N = 4, M = 4
{-1, -1, -1, 0},
{-1, -1, 3, -1},
{4, -1, 0, -1}};
输出
No
解释
这里，我们有 4 个岛屿，我们无法通过解除任何单个单元格的阻塞来连接它们。
方法
在此方法中，我们将遍历每个单元格。我们将为包含值 1 到 K 的所有单元格赋予一个数字，表示它属于哪个岛屿。
之后，我们将检查每个阻塞单元格，看看是否有任何阻塞单元格可以连接矩阵的所有岛屿。如果可能的话，我们可以通过解除单个单元格的阻塞来连接矩阵的所有单元格。
算法
步骤 1 - 定义 cells[k][2] 矩阵来存储包含值 1 到 K 的所有单元格索引，定义 vis[][] 矩阵来跟踪当前访问的单元格，并将 'cnt' 设置为 0。
步骤 2 - 遍历矩阵的每个单元格。如果当前单元格值不是 0 或 -1，则将 p 和 q 值插入 cells[][] 矩阵中的 'cnt' 索引处，并将 'cnt' 增加 1。此外，将 vis[p][q] 更新为 false。
步骤 3 - 定义 dx[] 和 dy[] 数组并存储所有四个水平和垂直方向。另外，用 0 初始化"集合"。
步骤 4 - 开始遍历 cell[][] 矩阵。
步骤 4.1 - 从第 p 个索引中获取行和列值，如果行和列单元格已被访问，则转到下一次迭代。
步骤 4.2 - 将集合增加 1 并定义队列以执行 BFS。
步骤 4.3 - 将行和列对插入队列。
步骤 4.4 - 在队列不为空时遍历。
步骤 4.4.1 - 从队列中弹出第一对，并使用"集合"更新单元格值值。
步骤 4.4.2 - 遍历所有四个方向。此外，检查边界条件，如果单元格已被访问或值为 -1，则转到下一次迭代。否则，在 vis[][] 矩阵中将当前对标记为已访问，并将它们插入队列。
步骤 5 - 现在，用 0 初始化 maxi 以存储任何单个阻塞单元可以连接的最大集合数。
步骤 6 - 开始遍历矩阵，如果当前单元值为 -1，请按照以下步骤操作。
步骤 6.1 - 定义集合以存储当前单元可以连接的岛屿数。
步骤 6.2 - 遍历所有四个方向并将除 0 和 -1 之外的所有唯一单元值存储在集合中。此处，单元格值是其所属岛屿的值。
步骤 6.3 - 如果集合大小大于最大值，则获取集合大小并更新最大值。
步骤 7 - 如果最大值等于集合，则打印"是"。否则，打印"否"。
示例
#include <bits/stdc++.h>
using namespace std;
#define pairs pair<int, int>
void connectable(int k, vector<vector<int>> mat, int n, int m) {
int cells[k][2];
bool vis[n][m];
int cnt = 0;
// 单元格矩阵初始化
for (int p = 0; p < n; p++) {
for (int q = 0; q < m; q++) {
if (mat[p][q] != 0 && mat[p][q] != -1) {
cells[cnt][0] = p;
cells[cnt][1] = q;
cnt++;
}
vis[p][q] = false;
}
}
// 方向
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// 存储不同集合的总数
int sets = 0;
// BFS 算法
for (int p = 0; p < k; p++) {
int row = cells[p][0], col = cells[p][1];
if (vis[row][col])
continue;
sets++;
queue<pairs> que;
que.push(make_pair(row, col));
vis[row][col] = true;
while (!que.empty()) {
pairs temp = que.front();
que.pop();
mat[temp.first][temp.second] = sets;
// 向四个方向移动
for (int q = 0; q < 4; q++) {
// 访问邻居单元格
int temp_x = temp.first + dx[q];
int temp_y = temp.second + dy[q];
if (temp_x < 0 || temp_x >= n || temp_y < 0 || temp_y >= m)
continue;
if (vis[temp_x][temp_y] || mat[temp_x][temp_y] == -1)
continue;
que.push(make_pair(temp_x, temp_y));
vis[temp_x][temp_y] = true;
}
}
}
int maxi = 0;
for (int p = 0; p < n; p++) {
for (int q = 0; q < m; q++) {
// 对于阻塞的单元格
if (mat[p][q] == -1) {
unordered_set<int> set;
for (int r = 0; r < 4; r++) {
int temp_x = p + dx[r];
int temp_y = q + dy[r];
if (temp_x < 0 || temp_x >= n || temp_y < 0 || temp_y >= m)
continue;
// 当元素不属于任何集合时
if (mat[temp_x][temp_y] <= 0)
continue;
set.insert(mat[temp_x][temp_y]);
}
int s = set.size();
maxi = max(s, maxi);
}
}
}
if (maxi == sets) {
cout << "是的，移除一个块后可以连接所有单元!";
} else {
cout << "不，不可能连接矩阵的所有单元!";
}
}
int main() {
int k = 6;
int n = 4, m = 4;
vector<vector<int>> mat = {{0, 2, 5, 0},
{-1, 6, -1, 3},
{-1, -1, 4, -1},
{0, -1, 1, -1}};
connectable(k, mat, n, m);
return 0;
}
输出
是的，移除一个块后可以连接所有单元!
时间复杂度− O(M*N)
空间复杂度 − O(M*N)
结论
我们为矩阵的每个单元赋予了一个唯一的设定编号，以便在下一步中，我们可以检查矩阵的特定阻塞单元可以连接多少个唯一的岛屿。
