数据结构
网络
关系数据库管理系统(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
广告