var detX = []int{1, -1, 1, -1, 2, -2, 2, -2}
var detY = []int{2, 2, -2, -2, 1, 1, -1, -1}

func knightProbability(N int, K int, r int, c int) float64 {
	dp := make([][]float64, N)
	for i := range dp {
		dp[i] = make([]float64, N)
	}
	dp[r][c] = 1.0
	for i := 0; i < K; i++ {
		ndp := make([][]float64, N)
		for j := range ndp {
			ndp[j] = make([]float64, N)
		}
		for y := 0; y < N; y++ {
			for x := 0; x < N; x++ {
				for j := 0; j < 8; j++ {
					ny, nx := y+detY[j], x+detX[j]
					if ny < 0 || N <= ny || nx < 0 || N <= nx {
						continue
					}
					ndp[y][x] += dp[ny][nx] / 8.0
				}
			}
		}
		dp = ndp
	}
	prob := 0.0
	for i := range dp {
		for _, p := range dp[i] {
			prob += p
		}
	}
	return prob
}