Giả sử chúng ta có mảng 2D nhị phân không rỗng gọi là grid, ở đây đảo là nhóm các 1 (đại diện cho đất liền) kết nối 4 chiều. Chúng ta cũng có thể giả định cả bốn cạnh của grid đều bị bao quanh bởi nước.
Chúng ta phải đếm số đảo khác nhau. Một đảo được coi là giống nhau nếu chúng có cùng hình dạng, hoặc có cùng hình dạng sau khi xoay 90, 180, hoặc 270 độ hoặc phản chiếu trái/phải hoặc lên/xuống.
Vì vậy, nếu đầu vào là như sau,
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
thì đầu ra sẽ là 1
Để giải quyết, chúng ta sẽ làm theo các bước:
Định nghĩa một map m
Định nghĩa hàm dfs(), nhận i, j, grid, idx,
nếu i và j trong phạm vi grid và grid[i,j] là 0 thì:
Trả về
grid[i, j] := 0
Chèn { i, j } vào cuối m[idx]
dfs(i + 1, j, grid, idx)
dfs(i - 1, j, grid, idx)
dfs(i, j - 1, grid, idx)
dfs(i, j + 1, grid, idx)
Định nghĩa hàm norm(), nhận mảng v
Định nghĩa mảng 2D s của cặp với 8 hàng
Khởi tạo i := 0, khi i < kích thước v, cập nhật (tăng i lên 1), làm:
x := v[i].first
y := v[i].second
Chèn { x, y } vào cuối s[0]
Chèn { x, -y } vào cuối s[1]
Chèn { - x, y } vào cuối s[2]
Chèn { - x, -y } vào cuối s[3]
Chèn { y, x } vào cuối s[4]
Chèn { y, -x } vào cuối s[5]
Chèn { - y, x } vào cuối s[6]
Chèn { - y, -x } vào cuối s[7]
Khởi tạo i := 0, khi i < kích thước s, cập nhật (tăng i lên 1), làm:
Sắp xếp mảng s[i]
Khởi tạo i := 0, khi i < kích thước s, cập nhật (tăng i lên 1), làm:
Khởi tạo j := 1, khi j < kích thước v, cập nhật (tăng j lên 1), làm:
s[i, j].first := s[i, j].first - s[i, 0].first
s[i, j].second := s[i, j].second - s[i, 0].second
s[i, 0].first := 0
s[i, 0].second := 0
Sắp xếp mảng s
Trả về s[0]
Từ phương thức main làm sau:
Định nghĩa một tập hợp pts
cnt := 1
Khởi tạo i := 0, khi i < kích thước grid, cập nhật (tăng i lên 1), làm:
Khởi tạo j := 0, khi j < kích thước grid[0], cập nhật (tăng j lên 1), làm &miuns;
nếu grid[i, j] giống 1, thì:
(tăng cnt lên 1)
dfs(i, j, grid, cnt)
Chèn norm(m[cnt]) vào pts
Trả về kích thước pts
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: map < int, vector < pair <int, int> > > m; void dfs(int i, int j, vector < vector <int> >& grid, int idx){ if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j]) return; grid[i][j] = 0; m[idx].push_back({ i, j }); dfs(i + 1, j, grid, idx); dfs(i - 1, j, grid, idx); dfs(i, j - 1, grid, idx); dfs(i, j + 1, grid, idx); } vector < pair <int, int> > norm(vector < pair < int, int > > v){ vector<vector<pair<int, int> > > s(8); for (int i = 0; i < v.size(); i++) { int x = v[i].first; int y = v[i].second; s[0].push_back({ x, y }); s[1].push_back({ x, -y }); s[2].push_back({ -x, y }); s[3].push_back({ -x, -y }); s[4].push_back({ y, x }); s[5].push_back({ y, -x }); s[6].push_back({ -y, x }); s[7].push_back({ -y, -x }); } for (int i = 0; i < s.size(); i++) { sort(s[i].begin(), s[i].end()); } for (int i = 0; i < s.size(); i++) { for (int j = 1; j < v.size(); j++) { s[i][j].first = s[i][j].first - s[i][0].first; s[i][j].second = s[i][j].second - s[i][0].second; } s[i][0].first = 0; s[i][0].second = 0; } sort(s.begin(), s.end()); return s[0]; } int numDistinctIslands2(vector<vector<int>>& grid) { set<vector<pair<int, int> > > pts; int cnt = 1; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 1) { cnt++; dfs(i, j, grid, cnt); pts.insert(norm(m[cnt])); } } } return pts.size(); } }; main(){ Solution ob; vector<vector<int>> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}; cout << (ob.numDistinctIslands2(v)); }Đầu vào
{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}Đầu ra
1