Leetcode 1568. Minimum Number of Days to Disconnect Island (python)

题目

解析：

这道题目的关键就在于，想到只有可能是0，1，2三种答案，想到了这个题目也就非常简单了

class Solution:def minDays(self, grid: List[List[int]]) -> int:# check if there is more than one disconnected islands in teh griddef check(curr_grid):start_pos = (-1,-1)for i in range(m):for j in range(n):if curr_grid[i][j] == 1:start_pos = (i,j)breakif start_pos == (-1,-1):return True# find one island firstq = collections.deque()q.append(start_pos)island = {
    start_pos:True}visited = [[False]*n for _ in range(m)]visited[start_pos[0]][start_pos[1]] = Truedirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j = q.popleft()for d in dirs:x = i + d[0]y = j + d[1]if 0<=x<m and 0<=y<n and not visited[x][y] and curr_grid[x][y]==1:q.append((x,y))visited[x][y] = Trueisland[(x,y)] = True# check again if there is any other islandfor i in range(m):for j in range(n):if curr_grid[i][j] == 1 and (i,j) not in island:return Truereturn Falsem = len(grid)n = len(grid[0])# check if there is only one islandif check(grid):return 0# check if remove 1 block can workfor i in range(m):for j in range(n):if grid[i][j] == 1:grid[i][j] = 0if check(grid):return 1grid[i][j] = 1# else return 2return 2

还可以通过检查一次访问到了多少个1的位置和grid一共有多少个1的位置来判断是否只包含一个island

class Solution:def minDays(self, grid: List[List[int]]) -> int:# check if there is more than one disconnected islands in teh griddef check(curr_grid):start_pos = (-1,-1)for i in range(m):for j in range(n):if curr_grid[i][j] == 1:start_pos = (i,j)breakif start_pos == (-1,-1):return -1# find one island firstq = collections.deque()q.append(start_pos)#island = {start_pos:True}visited = set()visited.add(start_pos)dirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j = q.popleft()for d in dirs:x = i + d[0]y = j + d[1]if 0<=x<m and 0<=y<n and (x,y) not in visited and curr_grid[x][y]==1:q.append((x,y))visited.add((x,y))#island[(x,y)] = True# check again if there is any other island# for i in range(m):# for j in range(n):# if curr_grid[i][j] == 1 and (i,j) not in island:# return Truereturn len(visited)m = len(grid)n = len(grid[0])candidate = []for i in range(m):for j in range(n):if grid[i][j] == 1:candidate.append((i,j))# check if there is only one islandtmp = check(grid)if tmp<len(candidate):return 0# check if remove 1 block can workfor i in range(m):for j in range(n):if grid[i][j] == 1:grid[i][j] = 0tmp = check(grid)if tmp<len(candidate)-1:return 1grid[i][j] = 1# else return 2return 2