package Graph
type Pos struct {
x, y int
}
// Queue is a generic type.
type Queue[T any] []T
// Size returns the number of elements in the queue.
func (q *Queue[T]) Size() int {
return len(*q)
}
// IsEmpty checks if the queue is empty.
func (q *Queue[T]) IsEmpty() bool {
return len(*q) == 0
}
// Enqueue adds an element to the back of the queue.
func (q *Queue[T]) Enqueue(e T) {
*q = append(*q, e)
}
// Dequeue removes and returns the element from the front of the queue.
func (q *Queue[T]) Dequeue() T {
if q.IsEmpty() {
var zero T // Return the zero value of type T if the queue is empty.
return zero
}
e := (*q)[0]
*q = (*q)[1:]
return e
}
// 时间复杂度: O(n * m), 空间复杂度: O(n * m)
func orangesRotting(grid [][]int) int {
n, m := len(grid), len(grid[0])
move := [5]int{-1, 0, 1, 0, -1}
queue := new(Queue[*Pos])
allZero := true
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] != 0 {
allZero = false
}
if grid[i][j] == 2 {
queue.Enqueue(&Pos{i, j})
}
}
}
if allZero {
return 0
}
curLevel := 0
for !queue.IsEmpty() {
curLevelSize := queue.Size()
for i := 0; i < curLevelSize; i++ {
curPos := queue.Dequeue()
curX, curY := curPos.x, curPos.y
for j := 0; j < 4; j++ {
nextX, nextY := curX+move[j], curY+move[j+1]
if nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && grid[nextX][nextY] == 1 {
grid[nextX][nextY] = 2
queue.Enqueue(&Pos{nextX, nextY})
}
}
}
curLevel++
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 1 {
return -1
}
}
}
return curLevel - 1
}