資料結構
網路
關係資料庫管理系統 (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 次瀏覽
