1091.二进制矩阵中的最短路径

func shortestPathBinaryMatrix(grid [][]int) int {
	n := len(grid)
	if grid[0][0] == 1 {
		return -1
	}
	if n == 1 {
		return 1
	}

	q := [][]int{}
	visited := make([][]bool, n)

	for i := 0; i < n; i++ {
		visited[i] = make([]bool, n)
	}
	visited[0][0] = true

	ans := -1
	var bfs func()
	var valid func(int, int) bool

	// row col
	q = append(q, []int{0, 0, 1})

	bfs = func() {
		for len(q) > 0 {
			curr := q[0]
			q = q[1:]

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

			for i := 0; i < 8; i++ {
				row := curr[0] + dy[i]
				col := curr[1] + dx[i]

				if valid(row, col) {
					visited[row][col] = true
					if row == n-1 && col == n-1 {
						ans = curr[2] + 1
					}
					q = append(q, []int{row, col, curr[2] + 1})
				}
			}
		}
	}

	valid = func(row, col int) bool {
		if row < 0 || col < 0 || row >= n || col >= n || visited[row][col] {
			return false
		}

		return grid[row][col] == 0
	}

	bfs()
	return ans
}

func powInt(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}