1이 육지를 나타내고 0이 물을 나타내는 이진 행렬이 있다고 가정합니다. 그리고 섬은 물로 둘러싸인 1의 그룹입니다. 가장 큰 섬의 크기를 찾아야 합니다. 최대 하나의 물 전지를 지상 전지로 변경할 수 있습니다.
따라서 입력이 다음과 같으면
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
그러면 출력은 7이 됩니다. 하나의 물 세포를 육지로 전환하여 두 섬을 연결할 수 있기 때문입니다. 따라서 최종 행렬은 다음과 같습니다. -
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
R :=매트의 행 개수, C :=매트의 열 개수
-
질량 :=새 지도
-
아이디 :=555
-
floodfill() 함수를 정의합니다. r, c, id가 필요합니다.
-
r과 c가 행렬의 범위에 있고 mat[r, c]가 1이면
-
매트[r, c] :=아이디
-
질량[id] :=질량[id] + 1
-
[(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ]의 각 쌍(r2, c2)에 대해
-
플러드필(r2, c2, id)
-
-
-
주요 방법에서 다음을 수행하십시오 -
-
0에서 R 사이의 r에 대해 수행
-
0에서 C 사이의 c에 대해 수행
-
mat[r, c]가 1과 같으면
-
아이디 :=아이디 + 1
-
질량[id] :=0
-
플러드필(r, c, id)
-
-
-
-
ans :=최대값(질량 및 1의 모든 값)
-
0 ~ R − 1 범위의 r에 대해
-
범위 0에서 C − 1까지의 c에 대해 수행
-
mat[r, c]가 0과 같지 않으면
-
다음 반복으로 이동
-
-
Island_set :=새로운 세트
-
[(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ]의 각 쌍(r2, c2)에 대해
-
r2와 c2가 mat의 범위에 있고 mat[r2, c2]가 1이면
-
Island_set에 mat[r2, c2] 추가
-
-
ans :=최대 ans 및 (1 + 각 섬 inisland_set에 대한 모든 질량[섬]의 합)
-
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, mat):
R, C = len(mat), len(mat[0])
mass = {}
id = 555
def floodfill(r, c, id):
nonlocal R, C, mat, mass
if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
mat[r][c] = id
mass[id] += 1
for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),
(r, c − 1)]:
floodfill(r2, c2, id)
for r in range(R):
for c in range(C):
if mat[r][c] == 1:
id += 1
mass[id] = 0
floodfill(r, c, id)
ans = max([val for val in mass.values()] + [1])
for r in range(R):
for c in range(C):
if mat[r][c] != 0:
continue
island_set = set()
for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),(r, c − 1)]:
if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
island_set.add(mat[r2][c2])
ans = max(ans, 1 + sum([mass[island] for island in island_set]))
return ans
ob = Solution()
matrix = [
[1, 0, 1],
[0, 0, 0],
[1, 1, 0],
[1, 1, 1]
]
print(ob.solve(matrix)) 입력
[ [1, 0, 1], [0, 0, 0], [1, 1, 0], [1, 1, 1] ]
출력
7