腐烂的橘子 -- DFS、BFS

994. 腐烂的橘子

class OrangesRotting:"""994. 腐烂的橘子https://leetcode.cn/problems/rotting-oranges/description/"""def solution(self, grid: List[List[int]]) -> int:"""BFS时间复杂度 O(M*N)空间复杂度 O(M*N):param grid::return:"""row, col, time = len(grid), len(grid[0]), 0directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]queue = []# add the rotten orange to the queuefor i in range(row):for j in range(col):if grid[i][j] == 2:queue.append((i, j, time))# bfswhile queue:i, j, time = queue.pop(0)for di, dj in directions:if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:grid[i + di][j + dj] = 2queue.append((i+di, j+dj, time+1))# if there are still fresh oranges, return -1for row in grid:if 1 in row:return -1return timedef solution1(self, grid: List[List[int]]) -> int:"""DFS时间复杂度 O((M*N)^2)空间复杂度 O(M*N):param grid::return:"""rows, cols = len(grid), len(grid[0])fresh = set()rotten = set()# Find positions of fresh and rotten orangesfor r in range(rows):for c in range(cols):if grid[r][c] == 1:fresh.add((r, c))elif grid[r][c] == 2:rotten.add((r, c))def dfs(r, c, minutes):# Check if position is valid and orange is freshif r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:return# If the current rotting time is less than the stored value# update it and continue DFS to adjacent orangesif (r, c) in fresh and minutes < self.time_to_rot.get((r, c), float('inf')):self.time_to_rot[(r, c)] = minutesdfs(r + 1, c, minutes + 1)dfs(r - 1, c, minutes + 1)dfs(r, c + 1, minutes + 1)dfs(r, c - 1, minutes + 1)# Dictionary to store the time taken to rot each fresh orangeself.time_to_rot = {}# Start DFS from each rotten orangefor r, c in rotten:dfs(r + 1, c, 1)dfs(r - 1, c, 1)dfs(r, c + 1, 1)dfs(r, c - 1, 1)# If there are fresh oranges that never rot, return -1if len(fresh) != len(self.time_to_rot):return -1# Return the maximum time taken to rot any fresh orangereturn max(self.time_to_rot.values(), default=0)