Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình tìm số nhóm tối thiểu trong tháp giao tiếp trong C ++?

Giả sử chúng ta có một ma trận nhị phân 2D trong đó 1 đại diện cho tháp truyền thông và 0 đại diện cho một ô trống. Các tháp có thể giao tiếp theo những cách sau:1. Nếu tháp A và tháp B nằm trên cùng một hàng hoặc cột, chúng có thể giao tiếp với nhau. 2. Nếu tháp A có thể nói chuyện với tháp B và tháp B có thể nói chuyện với C, thì A có thể nói chuyện với C (tính chất bắc cầu). Chúng ta phải tìm tổng số nhóm tháp có (ở đây một nhóm là danh sách các tháp có thể nói chuyện với nhau).

Vì vậy, nếu đầu vào giống như

1 1 0
0 0 1
1 0 1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

  • Xác định một hàm dfs (), điều này sẽ lấy một ma trận mảng 2D, i, j, n, m,

  • ma trận [i, j]:=2

  • để khởi tạo k:=1, khi k

    • p:=(i + k) mod n

    • q:=j

    • nếu ma trận [p, q] giống 1, thì:

      • dfs (ma trận, p, q, n, m)

  • để khởi tạo k:=1, khi k

    • p:=i

    • q =(j + k)

    • nếu ma trận [p, q] giống 1, thì:

      • dfs (ma trận, p, q, n, m)

  • Từ phương thức chính, thực hiện như sau:

  • n:=kích thước của ma trận

  • ans:=0

  • để khởi tạo i:=0, khi i

    • để khởi tạo j:=0, khi j

      • nếu ma trận [i, j] giống 1, thì:

        • (tăng ans lên 1)

        • dfs (ma trận, i, j, n, m)

  • trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ 

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

Đầu vào 

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

Đầu ra 

1