002.腐烂的橘子

• 994.腐烂的橘子
  • 多源广度优先搜索

腐烂的橘子 - 多源广度优先搜索

func orangesRotting(grid [][]int) int {
	n := len(grid)
	m := len(grid[0])
	ans := 0
	freshOrangesCount := 0
	queue := [][2]int{}
 
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				freshOrangesCount++
			} else if grid[i][j] == 2 {
				queue = append(queue, [2]int{ i, j })
			}
		}
	}
 
	for len(queue) > 0 {
		size := len(queue)
		for k := 0; k < size; k++ {
			i := queue[k][0]
			j := queue[k][1]
			if i > 0 && grid[i - 1][j] == 1 {
				grid[i - 1][j] = 2
				freshOrangesCount--
				queue = append(queue, [2]int{ i - 1, j })
			}
			if i < n - 1 && grid[i + 1][j] == 1 {
				grid[i + 1][j] = 2
				freshOrangesCount--
				queue = append(queue, [2]int{ i + 1, j })
			}
			if j > 0 && grid[i][j - 1] == 1 {
				grid[i][j - 1] = 2
				freshOrangesCount--
				queue = append(queue, [2]int{ i, j - 1 })
			}
			if j < m - 1 && grid[i][j + 1] == 1 {
				grid[i][j + 1] = 2
				freshOrangesCount--
				queue = append(queue, [2]int{ i, j + 1 })
			}
		}
		queue = queue[size:]
		if len(queue) > 0 {
			ans++
		}
	}
 
	if freshOrangesCount > 0 {
		return -1
	}
	return ans
}