python-leetcode题解第994题腐烂的橘子.zip

''' In a given grid, each cell can have one of three values: the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead. ''' class Solution(object): def valid(self, row, col, row_size, col_size): return row >= 0 and col >= 0 and row < row_size and col < col_size def orangesRotting(self, grid): """ :type grid: List[List[int]] :rtype: int """ queue = [] for row_index in range(len(grid)): for col_index in range(len(grid[0])): if grid[row_index][col_index] == 2: queue.append((row_index, col_index)) result = 0 queue.append((-1, -1)) while queue: flag = False print queue while(queue[0][0] != -1 and queue[0][1] != -1): (row, col) = queue[0] if self.valid(row+1, col, len(grid), len(grid[0])) and grid[row+1][col] == 1 : if not flag: result += 1 flag =True grid[row+1][col] = 2 row += 1 queue.append((row, col)) row -= 1 if self.valid(row-1, col, len(grid), len(grid[0])) and grid[row-1][col] == 1 : if not flag: result += 1 flag =True grid[row-1][col] = 2 row -= 1 queue.append((row, col)) row += 1 if self.valid(row, col+1, len(grid), len(grid[0])) and grid[row][col+1] == 1 : if not flag: result += 1 flag =True grid[row][col+1] = 2 col += 1 queue.append((row, col)) col -= 1 if self.valid(row, col-1, len(grid), len(grid[0])) and grid[row][col-1] == 1 : if not flag: result += 1 flag =True grid[row][col-1] = 2 col -= 1 queue.append((row, col)) col += 1 queue.pop(0) queue.pop(0) if queue: queue.append((-1, -1)) for row_index in range(len(grid)): for col_index in range(len(grid[0])): if grid[row_index][col_index] == 1: return -1 return result