数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查网格中编号为 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[] 数组并存储所有四个水平和垂直方向。同时，将 'sets' 初始化为 0。
步骤 4 − 开始遍历 cell[][] 矩阵。
步骤 4.1 − 从第 p 个索引获取行和列值，如果行和列单元格已被访问，则移动到下一个迭代。
步骤 4.2 − 将 sets 加 1 并定义队列以执行广度优先搜索 (BFS)。
步骤 4.3 − 将行和列对插入队列。
步骤 4.4 − 遍历队列不为空。
步骤 4.4.1 − 从队列中弹出第一对，并将单元格值更新为 'set' 值。
步骤 4.4.2 − 在所有四个方向上遍历。同时，检查边界条件，如果单元格已被访问或值为 -1，则移动到下一个迭代。否则，在 vis[][] 矩阵中将当前对标记为已访问，并将它们插入队列。
步骤 5 − 现在，将 maxi 初始化为 0 以存储任何单个阻塞单元格可以连接的最大集合数。
步骤 6 − 开始遍历矩阵，如果当前单元格值为 -1，则执行以下步骤。
步骤 6.1 − 定义一个集合来存储当前单元格可以连接的岛屿数量。
步骤 6.2 − 在所有四个方向上遍历，并将集合中所有唯一的单元格值（除 0 和 -1 外）存储在集合中。这里的单元格值是它所属岛屿的值。
步骤 6.3 − 获取集合大小，如果集合大小大于 maxi，则更新 maxi。
步骤 7 − 如果 maxi 等于 sets，则打印 'Yes'。否则，打印 'No'。
示例
#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;
// Cells matrix initialization
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;
}
}
// Directions
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// To store the total number of different sets
int sets = 0;
// BFS algorithm
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;
// Moving in each four direction
for (int q = 0; q < 4; q++) {
// Visiting neighbor cells
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++) {
// For blocked cell
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;
// When an element is not from any set
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 << "Yes, It is possible to connect all cells after removing one block!";
} else {
cout << "No, It is not possible to connect all cells of matrix!";
}
}
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;
}
输出
Yes, It is possible to connect all cells after removing one block!
时间复杂度 − O(M*N)
空间复杂度 − O(M*N)
结论
我们为矩阵的每个单元格赋予了一个唯一的集合编号，以便在下一步中，我们可以检查矩阵的特定阻塞单元格可以连接多少个唯一的岛屿。
50 次浏览
