grid라고 하는 비어 있지 않은 2D 이진 배열이 있다고 가정합니다. 여기에서 섬은 4방향으로 연결된 1(땅을 나타냄)의 그룹입니다. 그리드의 네 모서리 모두가 물로 둘러싸여 있다고 가정할 수도 있습니다.
우리는 별개의 섬의 수를 세어야 합니다. 섬은 모양이 같거나 90도, 180도, 270도만 회전하거나 왼쪽/오른쪽 또는 위/아래 방향이 반사된 후에도 모양이 같으면 다른 섬과 동일한 것으로 간주됩니다.
따라서 입력이 다음과 같으면
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
그러면 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 맵 정의
-
dfs() 함수를 정의하면 i, j, grid, idx,
가 필요합니다. -
i와 j가 그리드의 범위에 있고 grid[i,j]가 0이면 -
-
반환
-
-
그리드[i, j] :=0
-
m[idx]
끝에 { i, j } 삽입 -
dfs(i + 1, j, 그리드, idx)
-
dfs(i - 1, j, 그리드, idx)
-
dfs(i, j - 1, 그리드, idx)
-
dfs(i, j + 1, 그리드, idx)
-
하나의 함수 norm()을 정의하면 배열 v
가 필요합니다.-
8개의 행이 있는 쌍으로 구성된 하나의 2D 배열 정의
-
initialize i :=0의 경우 i
-
x :=v[i].첫 번째
-
y :=v[i].second
-
s[0]
끝에 { x, y } 삽입 -
s[1]
끝에 { x, -y } 삽입 -
s[2]
끝에 { - x, y } 삽입 -
s[3]
끝에 { - x, -y } 삽입 -
s[4]
끝에 { y, x } 삽입 -
s[5]
끝에 { y, -x } 삽입 -
s[6]
끝에 { - y, x } 삽입 -
s[7]
끝에 { - y, -x } 삽입
-
-
initialize i :=0의 경우, i
-
배열 s[i]
정렬
-
-
initialize i :=0의 경우, i
-
j 초기화의 경우:=1, 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].첫 번째 :=0
-
s[i, 0].초 :=0
-
-
배열 정렬
-
반환 s[0]
-
-
주요 방법에서 다음을 수행하십시오 -
-
한 세트 포인트 정의
-
cnt :=1
-
initialize i :=0의 경우, i <그리드 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
j 초기화의 경우:=0, j <그리드[0]의 크기일 때 업데이트(j를 1만큼 증가), &miuns;
수행-
grid[i, j]가 1과 같으면 -
-
(cnt를 1씩 증가)
-
dfs(i, j, 그리드, cnt)
-
pts에 표준(m[cnt]) 삽입
-
-
-
-
pts의 반환 크기
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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));
} 입력
{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}} 출력
1