994.Rotting Oranges（腐烂的橘子 ）

Description

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.

---

在给定的网格中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；

• 值 1 代表新鲜橘子；

• 值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

题目链接：https://leetcode.com/problems/rotting-oranges/

Difficulty: easy

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

• 1 <= grid.length <= 10
• 1 <= grid[0].length <= 10
• grid[i][j] is only 0, 1, or 2.

分析

• 用size记录好橘子的个数，每分钟（即每次循环）遍历所有坏橘子，将其周围的好橘子感染变坏，同时修改size值以及grid中相应的数字；
• 直至size等于0或者不再改变，停止循环；
• size等于零，返回time，反之，说明有橘子没有变坏，返回-1.

参考代码

class Solution(object):
def orangesRotting(self, grid):
    time=0
    size=0
    for row in grid:
        for col in row:
            if(col == 1):
                size+=1
    row=len(grid)
    col=len(grid[0])
    def get(x,y,gr):
        if(x-1>=0 and gr[x-1][y]==2):
            return True
        if(y-1>=0 and gr[x][y-1]==2):
            return True
        if(x+1<len(gr) and gr[x+1][y]==2):
            return True
        if(y+1<len(gr[0]) and gr[x][y+1]==2):
            return True
        return False
    import copy
    judge=True
    while(judge and size>0):
        judge=False
        new_grid=copy.deepcopy(grid)
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if(grid[row][col]==1 and get(row,col,grid)):
                    new_grid[row][col]=2
                    #print(row,col)
                    size-=1
                    judge=True
        grid=copy.deepcopy(new_grid)
        #print(grid)
        time+=1
    if(not judge):
        return -1
    return time