var dy []int = []int{0, 1, 0, -1}
var dx []int = []int{1, 0, -1, 0}

type pair struct {
	_1 int
	_2 int
}

func updateMatrix(matrix [][]int) [][]int {
	m := len(matrix)
	if m == 0 {
		return matrix
	}
	n := len(matrix[0])
	if n == 0 {
		return matrix
	}
	updated := make([][]bool, m)
	for i := range updated {
		updated[i] = make([]bool, n)
	}
	queue := make([]pair, 0)
	for y := 0; y < m; y++ {
		for x := 0; x < n; x++ {
			if matrix[y][x] == 0 {
				updated[y][x] = true
				continue
			}
			for i := 0; i < 4; i++ {
				ny, nx := y+dy[i], x+dx[i]
				if 0 <= ny && ny < m && 0 <= nx && nx < n && matrix[ny][nx] == 0 {
					updated[y][x] = true
					queue = append(queue, pair{y, x})
					break
				}
			}
		}
	}
	for len(queue) != 0 {
		p := queue[0]
		queue = queue[1:]
		val := matrix[p._1][p._2]
		for i := 0; i < 4; i++ {
			ny, nx := p._1+dy[i], p._2+dx[i]
			if 0 <= ny && ny < m && 0 <= nx && nx < n && !updated[ny][nx] {
				updated[ny][nx] = true
				queue = append(queue, pair{ny, nx})
				matrix[ny][nx] = val + 1
			}
		}
	}
	return matrix
}