package main

import "math"

type point struct {
	y, x int
}

func updateMatrix(mat [][]int) [][]int {
	m, n := len(mat), len(mat[0])
	dirs := []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
	// 找到任意0作为广搜起点
	zeroPoints := findZeros(mat)
	queue := make([]point, 0, 0)
	queue = append(queue, zeroPoints...)
	visited := map[int]bool{}
	res := initRes(mat)
	for len(queue) != 0 {
		top := queue[0]
		queue = queue[1:]
		if visited[top.x+top.y*n] {
			continue
		}
		visited[top.x+top.y*n] = true
		// 0 或 1 都可以更新mat值
		for _, dir := range dirs {
			ny, nx := top.y+dir.y, top.x+dir.x
			if ny < 0 || nx < 0 || ny >= m || nx >= n {
				continue
			}
			if mat[ny][nx] > 0 && res[ny][nx] > mat[top.y][top.x]+1 {
				res[ny][nx] = mat[top.y][top.x] + 1
				mat[ny][nx] = res[ny][nx]
			}
			if !visited[ny*n+nx] {
				queue = append(queue, point{ny, nx})
			}
		}
	}
	return res
}

// 将0保留，1变为正无穷
func initRes(mat [][]int) [][]int {
	m, n := len(mat), len(mat[0])
	res := make([][]int, m, m)
	for i := range res {
		res[i] = make([]int, n, n)
	}
	for i, arr := range mat {
		for j, v := range arr {
			if v == 1 {
				res[i][j] = math.MaxInt32
			}
		}
	}
	return res
}

// [2]int{y,x}
func findZeros(mat [][]int) (res []point) {
	for i, arr := range mat {
		for j, v := range arr {
			if v == 0 {
				res = append(res, point{i, j})
			}
		}
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {

}