C++ 检查在移除至多一个阻塞单元后，网格中编号为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的单元格分配一个数字，表示它属于哪个岛屿。

之后，我们将检查每个封锁的单元格，看看是否有任何封锁的单元格可以连接矩阵的所有岛屿。如果可能，我们可以通过解锁一个单元格来连接矩阵的所有单元格。

算法

• Step 1 - 定义cells[k][2]矩阵，用于存储索引包含1到K的所有单元格，定义vis[][]矩阵用于跟踪当前访问过的单元格，并将’cnt’初始化为0。

• Step 2 - 遍历矩阵的每个单元格。如果当前单元格的值不为0或-1，则在cells[][]矩阵的’cnt’索引处插入p和q的值，并将’cnt’增加1。同时，将vis[p][q]更新为false。

• Step 3 - 定义dx[]和dy[]数组，存储所有四个水平和垂直方向。同时，将’sets’初始化为0。

• Step 4 - 开始遍历cell[][]矩阵。

• Step 4.1 - 从第pth索引处获取行和列的值，如果行和列的单元格已经被访问过，则进入下一次迭代。

  • 第4.2步： − 将集合增加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，则打印“是”。否则，打印“否”。

  • 例子

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

结论

我们给矩阵的每个单元格都赋予了一个唯一的编号，这样在下一步中，我们可以检查由矩阵的特定阻塞单元格连接的唯一岛屿的数量。