สมมติว่าเรามีเมทริกซ์ไบนารี 2D โดย 1 แทนหอสื่อสาร และ 0 แทนเซลล์ว่าง หอสื่อสารสามารถสื่อสารได้ดังนี้: 1. ถ้าหอ A และหอ B อยู่แถวเดียวกันหรือคอลัมน์เดียวกัน พวกเขาสามารถสื่อสารได้ 2. ถ้าหอ A พูดกับ B ได้ และ B พูดกับ C ได้ แล้ว A พูดกับ C ได้ (สมบัติข้ามถัด) เราต้องหาจำนวนกลุ่มหอสื่อสารทั้งหมด (กลุ่มคือรายการหอที่พูดกันได้)
เช่น ถ้าอินพุตเป็น:
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
กำหนดฟังก์ชัน dfs() รับเมทริกซ์ 2D, i, j, n, m
matrix[i][j] := 2
ลูป k จาก 1 ถึง n-1:
p := (i + k) mod n
q := j
ถ้า matrix[p][q] เป็น 1 ให้ dfs(matrix, p, q, n, m)
ลูป k จาก 1 ถึง m-1:
p := i
q = (j + k) mod m
ถ้า matrix[p][q] เป็น 1 ให้ dfs(matrix, p, q, n, m)
จากเมธอดหลัก:
n := ขนาดของเมทริกซ์
ans := 0
ลูป i จาก 0 ถึง n-1:
ลูป j จาก 0 ถึง m-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
