994. 腐烂的橘子

[yankewei]

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

示例 1：

输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：

输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为 0、1 或 2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges

解法

首先这是一道广度优先搜索题，广度优先搜索是先把同级别的遍历完之后，再区走下一层，放到这个题，就是一个坏橘子的四周就是这个坏橘子的下一层。看到好多用递归的方式解决的，递归本来就挺绕的，这里 用队列区实现，我感觉要更容易理解一些。
1、声明一个队列，然后把矩阵中所有坏橘子放到队列中存储起来，因为是一个二维数组，需要两个地址才能确认
2、遍历队列，知道队列中的所有元素清空，清空后，就相当于把所有的坏橘子都感染了。要把被感染橘子的坐标放到另一个数组中，供下一次遍历
3、再遍历队列，知道队列清空之后
4、再次遍历矩阵即可

func orangesRotting(grid [][]int) int {
	row, column := len(grid)-1, len(grid[0])-1
	var ret int
	var tmp [][]int
	for i, v := range grid {
		for ii, vv := range v {
			if vv == 2 {
				tmp = append(tmp, []int{i, ii})
			}
		}
	}
	for len(tmp) != 0 {
		queue := make([][]int, len(tmp))
		copy(queue, tmp)
		tmp = tmp[0:0]

		hashGood := false
		for len(queue) != 0 {
			x := queue[0][0]
			y := queue[0][1]
			if y-1 >= 0 && grid[x][y-1] == 1 { // 坏橘子左边是好橘子
				hashGood = true
				grid[x][y-1] = 2
				tmp = append(tmp, []int{x, y - 1})
			}
			if x-1 >= 0 && grid[x-1][y] == 1 { // 坏橘子上边是好橘子
				hashGood = true
				grid[x-1][y] = 2
				tmp = append(tmp, []int{x - 1, y})
			}
			if y+1 <= column && grid[x][y+1] == 1 { // 坏橘子右边是好橘子
				hashGood = true
				grid[x][y+1] = 2
				tmp = append(tmp, []int{x, y + 1})
			}
			if x+1 <= row && grid[x+1][y] == 1 { // 坏橘子下边是好橘子
				hashGood = true
				grid[x+1][y] = 2
				tmp = append(tmp, []int{x + 1, y})
			}
			queue = queue[1:]
		}
		if hashGood {
			ret++
		}
	}

	for _, v := range grid {
		for _, vv := range v {
			if vv == 1 {
				return -1
			}
		}
	}
	return ret
}