Find Minimum Number of Groups in Communication Towers in C++

Suppose we have a 2D binary matrix where 1 represents a communication tower, and 0 represents an empty cell. The towers can communicate in the following ways: 1. If tower A, and tower B are either on the same row or column, they can communicate with each other. 2. If tower A can talk with tower B and B can talk with C, then A can talk to C (transitive property). We have to find the total number of tower groups there are (here a group is a list of towers that can talk with each other).

So, if the input is like

To solve this, we will follow these steps:

• Define a function dfs(), this will take one 2D array matrix, i, j, n, m,

• matrix[i, j] := 2

• for initialize k := 1, when k < n, update (increase k by 1), do:

  • p := (i + k) mod n

  • q := j

  • if matrix[p, q] is same as 1, then:

    • dfs(matrix, p, q, n, m)

• for initialize k := 1, when k < m, update (increase k by 1), do:

  • p := i

  • q = (j + k)

  • if matrix[p, q] is same as 1, then:

    • dfs(matrix, p, q, n, m)

• From the main method do the following:

• n := size of matrix

• ans := 0

• for initialize i := 0, when i < n, update (increase i by 1), do:

  • for initialize j := 0, when j < m, update (increase j by 1), do:

    • if matrix[i, j] is same as 1, then:

      • (increase ans by 1)

      • dfs(matrix, i, j, n, m)

• return ans

Let us see the following implementation to get better understanding:

Example

 Live Demo

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

Input

{{1,1,0},
{0,0,1},
{1,0,1}};

Output

1