1568. Minimum Number of Days to Disconnect Island
## 思路
計算components的數量
如果數量不是1 就直接回傳0
只有一個component時, 會有三種可能:
00000
00100
00000 <- 刪掉1之後 component=0
11111
11011
00000 <- 其中有一個1轉0之後可以把component切成兩個
11111
11111
11111 <- 把最角落的1相鄰的兩個1 轉0之後可以把component切成兩個
掃整個grid, 把1轉0之後檢查component數量
如果component數量不為1 就回傳1
都不行就回傳2
## Code
```python
class Solution:
def minDays(self, grid: List[List[int]]) -> int:
len_r, len_c = len(grid), len(grid[0])
def get_components():
res = 0
seen = set()
def dfs(r, c):
seen.add((r, c))
for nr, nc in (r+1, c), (r-1, c), (r, c-1), (r, c+1):
if (
0 <= nr < len_r and 0 <= nc < len_c
and grid[nr][nc] and (nr, nc) not in seen
):
dfs(nr, nc)
for r in range(len_r):
for c in range(len_c):
if grid[r][c] == 0 or (r, c) in seen:
continue
dfs(r, c)
res += 1
return res
if get_components() != 1:
return 0
for r in range(len_r):
for c in range(len_c):
if grid[r][c] == 0:
continue
grid[r][c] = 0
if get_components() != 1:
return 1
grid[r][c] = 1
return 2
```