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
```