하나의 무한한 물 격자가 있다고 가정합니다. 그리드에 토지 블록을 하나씩 추가할 수 있습니다. 우리는 각 좌표가 [r, c] 형식인 land_requests라는 좌표 목록을 가지고 있습니다. 여기서 r은 행이고 c는 열입니다. land_requests에서 각 토지 블록을 추가한 후 각 요소가 존재하는 섬의 수를 나타내는 목록을 찾아야 합니다.
따라서 입력이 land_requests =[[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]]과 같으면 출력은 [1, 2 , 2, 2, 1]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
d :=[(−1, 0) ,(0, 1) ,(1, 0) ,(0, −1) ]
와 같은 방향 목록 -
아이디:=0
-
mp :=새 지도
-
p :=새 목록
-
크기 :=새 목록
-
비교 :=0
-
ans :=새 목록
-
search() 함수를 정의합니다. 이것은 당신을 걸릴 것입니다
-
u가 p[u]와 같으면
-
돌아오다
-
p[u] :=검색(p[u])
-
-
반환 p[u]
-
connect() 함수를 정의합니다. 이것은 당신을 걸릴 것입니다, v
-
pu :=검색(u), pv :=검색(v)
-
pu가 pv와 같으면
-
반환
-
-
comp :=comp − 1
-
크기[pu]>=크기[pv]이면
-
p[pv] :=푸
-
크기[pu] :=크기[pu] + 크기[pv]
-
-
그렇지 않으면
-
p[pu] :=pv
-
크기[pv] :=크기[pv] + 크기[pu]
-
-
주요 방법에서 다음을 수행하십시오 -
-
land_requests의 각 요청에 대해
-
(i, j) :=요청
-
mp[i, j] :=idx
-
p
끝에 idx 삽입 -
크기 끝에 1 삽입
-
idx :=idx + 1
-
comp :=comp + 1
-
d의 각 k에 대해 수행
-
ni :=i + k[1]
-
nj :=j + k[0]
-
(ni, nj)가 mp이면
-
연결(mp[(i,j)], mp[(ni,nj)])
-
-
-
ans의 끝에 comp 삽입
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
d = [(−1, 0), (0, 1), (1, 0), (0, −1)] class Solution: def search(self, u): if u == self.p[u]: return u self.p[u] = self.search(self.p[u]) return self.p[u] def connect(self, u, v): pu = self.search(u) pv = self.search(v) if pu == pv: return self.comp −= 1 if self.size[pu] >= self.size[pv]: self.p[pv] = pu self.size[pu] += self.size[pv] else: self.p[pu] = pv self.size[pv] += self.size[pu] def solve(self, land_requests): self.idx = 0 self.mp = dict() self.p = [] self.size = [] self.comp = 0 ans = [] for request in land_requests: i, j = request self.mp[(i, j)] = self.idx self.p.append(self.idx) self.size.append(1) self.idx += 1 self.comp += 1 for k in d: ni = i + k[1] nj = j + k[0] if (ni, nj) in self.mp: self.connect(self.mp[(i, j)], self.mp[(ni, nj)]) ans.append(self.comp) return ans ob = Solution() land_requests = [[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]] print(ob.solve(land_requests))
입력
[[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]]
출력
[1, 2, 2, 2, 1]