腐烂的苹果

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param grid int整型二维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34?tpId=196&tqId=40529&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        典型的广搜
        初始化：
            将所有grid[i][j] == 2的坐标加入队列queue， count = 0
        当queue不空时，进行如下处理：
            count += 1
            遍历queue，向上下左右四个方向，有完整的苹果的位置进行扩展，标记扩展几点为grid[i][j]=2，记录扩展坐标至newQueue
            遍历结束，将newQueue赋值给queue
        返回值：count
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def rotApple(self, grid):
        # write code here
        m, n = len(grid), len(grid[0])

        queue, hashMap = [], set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:  # 初始，记录所有腐烂苹果的坐标
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    hashMap.add((i, j))

        count, directions = -1, [(0, 1), (1, 0), (0, -1), (-1, 0)]
        while queue:
            newQueue = []
            count += 1
            for x, y in queue:
                for i, j in directions:
                    tx, ty = x + i, y + j
                    if tx < 0&nbs***bsp;tx >= m&nbs***bsp;ty < 0&nbs***bsp;ty >= n&nbs***bsp;grid[tx][ty] != 1:
                        continue
                    grid[tx][ty] = 2
                    hashMap.remove((tx, ty))
                    newQueue.append((tx, ty))
            queue = newQueue
        return count if not hashMap else -1


if __name__ == "__main__":
    sol = Solution()

    matrix = [[2, 1, 1], [1, 0, 1], [1, 1, 1]]

    # matrix = [[2, 1, 0], [1, 0, 1], [0, 0, 0]]

    res = sol.rotApple(matrix)

    print res