Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/11 20:36)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串694/1548 (看更多)

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 ``` -- http://i.imgur.com/OLvBn3b.jpg