資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++程式：查詢通訊塔中分組的最小數量？
假設我們有一個二維二進位制矩陣，其中1表示通訊塔，0表示空單元格。塔之間可以以以下方式通訊：1. 如果塔A和塔B位於同一行或同一列，則它們可以相互通訊。2. 如果塔A可以與塔B通訊，而塔B可以與塔C通訊，則塔A可以與塔C通訊（傳遞性）。我們必須找到通訊塔的總組數（這裡一個組是一組可以相互通訊的塔）。
因此，如果輸入如下所示：
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
為了解決這個問題，我們將遵循以下步驟：
定義一個函式dfs()，它將接收一個二維陣列矩陣、i、j、n、m作為引數。
matrix[i, j] := 2
初始化k := 1，當k < n時，更新（k自增1），執行：
p := (i + k) mod n
q := j
如果matrix[p, q]等於1，則：
dfs(matrix, p, q, n, m)
初始化k := 1，當k < m時，更新（k自增1），執行：
p := i
q := (j + k)
如果matrix[p, q]等於1，則：
dfs(matrix, p, q, n, m)
在主方法中執行以下操作：
n := 矩陣的大小
ans := 0
初始化i := 0，當i < n時，更新（i自增1），執行：
初始化j := 0，當j < m時，更新（j自增1），執行：
如果matrix[i, j]等於1，則：
(ans自增1)
dfs(matrix, i, j, n, m)
返回ans
讓我們看下面的實現來更好地理解
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(vector<vector<int>>& matrix, int i, int j, int& n, int& m) {
matrix[i][j] = 2;
for (int k = 1; k < n; k++) {
int p = (i + k) % n, q = j;
if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
}
for (int k = 1; k < m; k++) {
int p = i, q = (j + k) % m;
if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
}
}
int solve(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
ans++;
dfs(matrix, i, j, n, m);
}
}
}
return ans;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
main(){
vector<vector<int>> v = {
{1,1,0},
{0,0,1},
{1,0,1}
};
cout << solve(v);
}輸入
{{1,1,0},
{0,0,1},
{1,0,1}};輸出
1
更新於：2020年11月10日
瀏覽量：156
廣告