994. 腐烂的橘子

思路
s:未被感染的橘子总数
q：装着当前腐烂的橘子位置（如二叉树的层级遍历 ）
next:腐烂橘子要感染的橘子（即为下一次腐烂的橘子）
先找出未被感染的橘子总数s,找出已腐烂的橘子作为第一层，这一层（当前q）的橘子同时在1分钟内分别去感染相邻未腐烂的橘子，即遍历结束q,只要有感染（不管有多少个腐烂橘子去感染未腐烂的），时间+1
ps:可按二叉树层级遍历来理解（102. 二叉树的层序遍历）
q装的是当前层的结点，next装的是下一层的结点
第一层：q=[root]
则遍历q的时候，把q.left、q.right装进next中，遍历q(当前层）结束后，将下一层赋予q，即q=next，继续重复操作

class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row=len(grid)
        col =len(grid[0])
        count = 0
        s=0
        q=[]
        for i in range(row):
            for j in range(col):
                if grid[i][j]==2:
                    q.append([i,j])
                if grid[i][j]==1:
                    s+=1
        while q:
            next =[]
            flag = False
            for t in q:
                i =t[0]
                j = t[1]
                if i-1>=0 and grid[i-1][j]==1:
                    grid[i-1][j]=2
                    next.append([i-1,j])
                    s-=1
                    flag=True
                if i+1<row and grid[i+1][j]==1:
                    grid[i+1][j]=2
                    next.append([i+1,j])
                    s-=1
                    flag=True
                if j-1>=0 and grid[i][j-1]==1:
                    grid[i][j-1]=2
                    next.append([i,j-1])
                    s-=1
                    flag=True
                if j+1<col and grid[i][j+1]==1:
                    grid[i][j+1]=2
                    next.append([i,j+1])
                    s-=1
                    flag=True
            if flag:
                count+=1
            
            q=next
        if s==0:
            return  count     
        else:
            return -1

二叉树的层序遍历
https://blog.csdn.net/huanxianxianshi/article/details/142331715

原文地址：https://blog.csdn.net/huanxianxianshi/article/details/142435080

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！