Python算法题源代码-LeetCode(力扣)-腐烂的橘子

# -*- coding:utf-8 -*- # Author='长孤秋落' '2024/2/21' # 博客：https://blog.csdn.net/weixin_36928396?type=blog # may the odds be ever in your favor """ 994. 腐烂的橘子 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。 示例 1： 输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4 示例 2： 输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。 示例 3： 输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。 提示： m == grid.length n == grid[i].length 1 <= m, n <= 10 grid[i][j] 仅为 0、1 或 2 """ import CheckFuncPerf as cfp class Solution: def orangesRotting_base(self, grid): directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] imaxrow, imaxcol = len(grid), len(grid[0]) queue = [] for rowidx in range(imaxrow): for colidx in range(imaxcol): if grid[rowidx][colidx] == 2: queue.append((rowidx, colidx, 0)) maxround = 0 while queue: rowidx, colidx, maxround = queue.pop(0) for delta in directions: nextrow, nextcol = rowidx+delta[0], colidx+delta[1] if 0 <= nextrow < imaxrow and 0 <= nextcol < imaxcol: if grid[nextrow][nextcol] == 1: grid[nextrow][nextcol] = 2 queue.append((nextrow, nextcol, maxround + 1)) for rowidx in range(imaxrow): for colidx in range(imaxcol): if grid[rowidx][colidx] == 1: return -1 return maxround def orangesRotting_ext1(self, grid): from collections import deque directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] imaxrow, imaxcol = len(grid), len(grid[0]) queue = deque([]) for rowidx in range(imaxrow): for colidx in range(imaxcol): if grid[rowidx][colidx] == 2: queue.append((rowidx, colidx, 0)) maxround = 0 while queue: rowidx, colidx, maxround = queue.popleft() for delta in directions: nextrow, nextcol = rowidx+delta[0], colidx+delta[1] if 0 <= nextrow < imaxrow and 0 <= nextcol < imaxcol: if grid[nextrow][nextcol] == 1: grid[nextrow][nextcol] = 2 queue.append((nextrow, nextcol, maxround + 1)) for rowidx in range(imaxrow): for colidx in range(imaxcol): if grid[rowidx][colidx] == 1: return -1 return maxround def orangesRotting_ext2(self, grid): from collections import deque directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] imaxrow, imaxcol = len(grid), len(grid[0]) queue = deque([]) for rowidx, row in enumerate(grid): for colidx, val in enumerate(row): if val == 2: queue.append((rowidx, colidx, 0)) maxround = 0 while queue: rowidx, colidx, maxround = queue.popleft() for delta in directions: nextrow, nextcol = rowidx + delta[0], colidx + delta[1] if 0 <= nextrow < imaxrow and 0 <= nextcol < imaxcol: if grid[nextrow][nextcol] == 1: grid[nextrow][nextcol] = 2 queue.append((nextrow, nextcol, maxround + 1)) if any(1 in row for row in grid): return -1 return maxround def orangesRotting_ext3(self, grid): from collections import deque imaxrow, imaxcol = len(grid), len(grid[0]) queue = deque() for rowidx, row in enumerate(grid): for colidx, val in enumerate(row): if val == 2: queue.append((rowidx, colidx, 0)) def validneighbors(irow, icol) -> (int, int): for newrow, newcol in ((irow - 1, icol), (irow, icol - 1), (irow + 1, icol), (irow, icol + 1)): if 0 <= newrow < imaxrow and 0 <= newcol < imaxcol: yield newrow, newcol maxround = 0 while queue: rowidx, colidx, maxround = queue.popleft() for nextrow, nextcol in validneighbors(rowidx, colidx): if grid[nextrow][nextcol] == 1: grid[nextrow][nextcol] = 2 queue.append((nextrow, nextcol, maxround + 1)) if any(1 in row for row in grid): return -1 return maxround if __name__ == '__main__': print('Hot52.py') # 功能测试 # grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] # aSolution = Solution() # print(aSolution.orangesRotting_base(grid)) # 超时测试 import random, copy imaxrow, imaxcol = 500, 500 list_originworld = [[random.randint(0, 9) for y in range(imaxcol)] for x in range(imaxrow)] for rowidx, row in enumerate(list_originworld): for colidx, val in enumerate(row): if val > 2: list_originworld[rowidx][colidx] = 1 aSolution = Solution() list_world = copy.deepcopy(list_originworld) result = cfp.getTimeMemoryStr(Solution.orangesRotting_base, aSolution, list_world) print(result['msg'], '执行结果 = {}'.format(result['result'])) list_world = copy.deepcopy(list_originworld) result = cfp.getTimeMemoryStr(Solution.orangesRotting_ext1, aSolution, list_world) print(result['msg'], '执行结果 = {}'.format(result['result'])) list_world = copy.deepcopy(list_originworld) result = cfp.getTimeMemoryStr(Solution.orangesRotting_ext2, aSolution, list_world) print(result['msg'], '执行结果 = {}'.format(result['result'])) list_world = copy.deepcopy(list_originworld) result = cfp.getTimeMemoryStr(Solution.orangesRotting_ext3, aSolution, list_world) print(result['msg'], '执行结果 = {}'.format(result['result']))