Giả sử chúng ta có một mảng nhị phân 2D không trống được gọi là lưới, ở đây một hòn đảo là một nhóm gồm 1 (đại diện cho đất) được kết nối 4 hướng. Chúng ta cũng có thể giả định rằng tất cả bốn cạnh của lưới đều được bao quanh bởi nước.
Chúng tôi phải đếm số lượng các hòn đảo khác nhau. Một hòn đảo được coi là giống với hòn đảo khác nếu chúng có cùng hình dạng hoặc có cùng hình dạng sau khi quay 90, 180 hoặc 270 độ hoặc chỉ phản chiếu theo hướng trái / phải hoặc hướng lên / xuống.
Vì vậy, nếu đầu vào giống như,
| 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 vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ m
-
Xác định một hàm dfs (), hàm này sẽ lấy i, j, grid, idx,
-
nếu tôi và j nằm trong phạm vi của lưới và lưới [i, j] bằng 0 thì -
-
trở lại
-
-
lưới [i, j]:=0
-
chèn {i, j} vào cuối m [idx]
-
dfs (i + 1, j, lưới, idx)
-
dfs (i - 1, j, lưới, idx)
-
dfs (i, j - 1, grid, idx)
-
dfs (i, j + 1, lưới, idx)
-
Xác định một hàm chuẩn (), điều này sẽ lấy một mảng v
-
Xác định một cặp dãy 2D có 8 hàng
-
để khởi tạo i:=0, khi i
-
x:=v [i]. đầu tiên
-
y:=v [i]. giây
-
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
-
sắp xếp mảng s [i]
-
-
để khởi tạo i:=0, khi i
-
để khởi tạo j:=1, khi 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
-
-
sắp xếp mảng s
-
trả về [0]
-
-
Từ phương thức chính, thực hiện như sau -
-
Xác định một nhóm pts
-
cnt:=1
-
để khởi tạo i:=0, khi i
-
để khởi tạo j:=0, khi j
-
nếu lưới [i, j] giống 1, thì -
-
(tăng cnt lên 1)
-
dfs (i, j, grid, cnt)
-
chèn định mức (m [cnt]) vào pts
-
-
-
-
kích thước trả về của pts
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:
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