C ++の通信塔で最小数のグループを見つけるプログラム？

1が通信塔を表し、0が空のセルを表す2Dバイナリ行列があるとします。タワーは次の方法で通信できます。1。タワーAとタワーBが同じ行または列にある場合、それらは互いに通信できます。 2.タワーAがタワーBと通信でき、BがCと通信できる場合、AはC（推移的プロパティ）と通信できます。そこにあるタワーグループの総数を見つける必要があります（ここで、グループは互いに会話できるタワーのリストです）。

したがって、入力が次のような場合

これを解決するには、次の手順に従います。

• 関数dfs（）を定義します。これは、1つの2D配列行列i、j、n、m、

  を取ります。

• matrix [i、j]：=2

• 初期化k：=1の場合、k

  • p：=（i + k）mod n

  • q：=j

  • matrix [p、q]が1と同じ場合、次のようになります。

    • dfs（行列、p、q、n、m）

• 初期化k：=1の場合、k

  • p：=i

  • q =（j + k）

  • matrix [p、q]が1と同じ場合、次のようになります。

    • dfs（行列、p、q、n、m）

• メインの方法から、次の手順を実行します。

• n：=行列のサイズ

• ans：=0

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • matrix [i、j]が1と同じ場合、次のようになります。

      • （ansを1増やします）

      • dfs（行列、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