Given an NxN chessboard and a Knight at position (x, y). The Knight has to take exactly K steps, where at each step it chooses any of the 8 directions uniformly at random. Find the probability that the Knight remains in the chessboard after taking K steps, with the condition that it cant enter the board again once it leaves it.
 
Example 1:
Input : N = 8, x = 0, y = 0, K = 3
Output: 0.125000
Example 2:
Input: N = 4, x = 1, y = 2, k = 4
Output: 0.024414
 
Your Task: 
You don't need to read or print anything. Your task is to complete the function findProb() which takes N, x, y and K as input parameter and returns the probability.
 
Expected Time Complexity : O(N ^{3})
Expected Space Complexity: O(N^{3})
 
Constraints:
1 <= N <= 100
0 <= x, y <= N
0 <= K <= N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def findProb(self, N, start_x, start_y, steps):

		# Code here

Solutions:
from functools import lru_cache

class Solution:

	def findProb(self, n, r, c, k):
		dir = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

		@lru_cache(None)
		def solve(x, y, t):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if t == 0:
				return 1
			ans = 0
			for (i, j) in dir:
				ans += solve(x + i, y + j, t - 1)
			return ans
		return solve(r, c, k) / 8 ** k


class Solution:

	def helper(self, start_x, start_y, dir_x, dir_y, dp, steps, N):
		if start_x >= 0 and start_x < N and (start_y >= 0) and (start_y < N) and (steps == 0):
			return 1
		if start_x < 0 or start_x >= N or start_y < 0 or (start_y >= N):
			return 0
		if dp[start_x][start_y][steps] != -1:
			return dp[start_x][start_y][steps]
		else:
			total_moves = 0
			for i in range(8):
				total_moves += self.helper(start_x + dir_x[i], start_y + dir_y[i], dir_x, dir_y, dp, steps - 1, N) * (1 / 8)
			dp[start_x][start_y][steps] = total_moves
			return dp[start_x][start_y][steps]

	def findProb(self, N, start_x, start_y, steps):
		dir_x = [-2, -2, -1, -1, 1, 1, 2, 2]
		dir_y = [-1, 1, -2, 2, -2, 2, -1, 1]
		dp = [[[-1 for i in range(steps + 1)] for i in range(N + 1)] for i in range(N + 1)]
		return self.helper(start_x, start_y, dir_x, dir_y, dp, steps, N)


from collections import defaultdict

class Solution:

	def findProb(self, N, row, column, k):
		n = N
		directions = [(-2, -1), (-1, -2), (1, -2), (2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)]
		memo = {}

		def dfs(i, j, k):
			if k == 0:
				return 1
			if (i, j, k) in memo:
				return memo[i, j, k]
			p = 0
			for (di, dj) in directions:
				x = i + di
				y = j + dj
				if x >= 0 and x < n and (y >= 0) and (y < n):
					p += dfs(x, y, k - 1) / 8
			memo[i, j, k] = p
			memo[n - 1 - i, j, k] = p
			memo[i, n - 1 - j, k] = p
			memo[n - 1 - i, n - 1 - j, k] = p
			return p
		return dfs(row, column, k)


from functools import lru_cache

class Solution:

	def findProb(self, n, start_x, start_y, steps):
		dir = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

		@lru_cache(None)
		def solve(x, y, t):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if t == 0:
				return 1
			ans = 0
			for (i, j) in dir:
				ans += solve(x + i, y + j, t - 1)
			return ans
		return solve(start_x, start_y, steps) / 8 ** steps


def rec(N, x, y, k, dp):
	if x >= N or x < 0 or y >= N or (y < 0):
		return 0
	elif k < 0:
		return 1
	elif dp[x][y][k] != -1:
		return dp[x][y][k]
	prob = 0
	dx = [-1, -1, -2, -2, 1, 1, 2, 2]
	dy = [-2, 2, -1, 1, 2, -2, 1, -1]
	for i in range(8):
		prob += rec(N, x + dx[i], y + dy[i], k - 1, dp) / 8.0
	dp[x][y][k] = prob
	return dp[x][y][k]

class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dp = [[[-1 for i in range(steps)] for j in range(N)] for k in range(N)]
		return rec(N, start_x, start_y, steps - 1, dp)


from functools import lru_cache

class Solution:

	def is_valid(self, n, x, y):
		if x < 0 or x >= n or y < 0 or (y >= n):
			return False
		return True

	def sol(self, x, y, t, n):
		dir = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

		@lru_cache(None)
		def solve(x, y, t):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if t == 0:
				return 1
			ans = 0
			for (i, j) in dir:
				ans += solve(x + i, y + j, t - 1)
			return ans
		return solve(x, y, t)

	def findProb(self, N, start_x, start_y, steps):
		return self.sol(start_x, start_y, steps, N) / 8 ** steps


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dirs = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
		dp = [[0] * N for _ in range(N)]
		dp[start_x][start_y] = 1
		for _ in range(steps):
			newDp = [[0] * N for _ in range(N)]
			for i in range(N):
				for j in range(N):
					for (dx, dy) in dirs:
						x = i + dx
						y = j + dy
						if 0 <= x < N and 0 <= y < N:
							newDp[i][j] += dp[x][y]
			dp = newDp
		return sum(map(sum, dp)) / 8 ** steps


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dp = [[[-1 for i in range(steps + 1)] for j in range(N)] for k in range(N)]

		def recurs(i, j, s, dp):
			if i < 0 or i >= N or j < 0 or (j >= N):
				return 0
			elif dp[i][j][s] != -1:
				return dp[i][j][s]
			elif s == 0:
				dp[i][j][s] = 1
				return 1
			else:
				su = 0
				for a in [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]:
					su += recurs(i + a[0], j + a[1], s - 1, dp)
				dp[i][j][s] = su / 8
				return su / 8
		recurs(start_x, start_y, steps, dp)
		return dp[start_x][start_y][steps]


import numpy as np

class Solution:

	def print_prob_arr(self, prob_arr, N, steps):
		for i in range(steps + 1):
			print('step: {}'.format(i))
			for x in range(N + 4):
				s = ''
				for y in range(N + 4):
					s += '{:.3f} '.format(prob_arr[i, x, y])
				print(s)

	def findProb(self, N, start_x, start_y, steps):
		prob_arr = np.zeros((steps + 1, N + 4, N + 4), dtype=float)
		prob_arr[0, 2:-2, 2:-2] = 1
		for i in range(1, steps + 1):
			for x in range(2, N + 2):
				for y in range(2, N + 2):
					prob_arr[i, x, y] = 0.125 * (prob_arr[i - 1, x + 2, y - 1] + prob_arr[i - 1, x + 2, y + 1] + prob_arr[i - 1, x + 1, y + 2] + prob_arr[i - 1, x + 1, y - 2] + prob_arr[i - 1, x - 2, y - 1] + prob_arr[i - 1, x - 2, y + 1] + prob_arr[i - 1, x - 1, y + 2] + prob_arr[i - 1, x - 1, y - 2])
		return prob_arr[steps, start_x + 2, start_y + 2]


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dx = [1, 2, 2, 1, -1, -2, -2, -1]
		dy = [2, 1, -1, -2, -2, -1, 1, 2]

		def inside(x, y):
			return x >= 0 and x < N and (y >= 0) and (y < N)
		dp1 = [[[0 for i in range(steps + 5)] for j in range(N + 5)] for k in range(N + 5)]
		for i in range(N):
			for j in range(N):
				dp1[i][j][0] = 1
		for s in range(1, steps + 1):
			for x in range(N):
				for y in range(N):
					prob = 0.0
					for i in range(8):
						nx = x + dx[i]
						ny = y + dy[i]
						if inside(nx, ny):
							prob += dp1[nx][ny][s - 1] / 8.0
					dp1[x][y][s] = prob
		return dp1[start_x][start_y][steps]


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dp = [[[0] * (steps + 1) for _ in range(N)] for _ in range(N)]
		dp[start_x][start_y][0] = 1
		di = [[1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2]]
		for move in range(1, steps + 1):
			for i in range(len(dp)):
				for j in range(len(dp[0])):
					for v in di:
						x = i + v[0]
						y = j + v[1]
						if x >= 0 and x < N and (y >= 0) and (y < N):
							dp[x][y][move] += dp[i][j][move - 1] / 8
		ans = 0
		for i in range(len(dp)):
			for j in range(len(dp[0])):
				ans += dp[i][j][steps]
		return ans


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		r = start_x
		c = start_y
		n = N
		curr = [[0] * n for j in range(n)]
		next1 = [[0] * n for j in range(n)]
		direction = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
		curr[r][c] = 1
		for k in range(steps):
			for i in range(n):
				for j in range(n):
					if curr[i][j] != 0:
						for d in direction:
							ni = i + d[0]
							nj = j + d[1]
							if 0 <= ni < n and 0 <= nj < n:
								next1[ni][nj] += curr[i][j] / 8
			curr = next1
			next1 = [[0] * n for j in range(n)]
		sum1 = 0
		for i in range(n):
			for j in range(n):
				sum1 += curr[i][j]
		return sum1


class Solution:

	def findProb(self, N, x, y, k):
		dir = [(2, 1), (-2, 1), (2, -1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]

		def isvalid(i, j):
			return i >= 0 and i <= N - 1 and (j >= 0) and (j <= N - 1)
		memo = {}

		def dfs(i, j, k):
			if (i, j, k) in memo:
				return memo[i, j, k]
			if not isvalid(i, j):
				return 0
			if k == 0:
				return 1
			prob = 0
			for (x, y) in dir:
				prob += dfs(i + x, j + y, k - 1)
			prob *= 0.125
			memo[i, j, k] = prob
			return prob
		return dfs(x, y, k)


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dp = [[[-1 for _ in range(steps + 1)] for _ in range(N)] for _ in range(N)]
		for i in range(N):
			for j in range(N):
				dp[i][j][0] = 1
		res = self.DFS(dp, N, steps, start_x, start_y) / 8 ** steps
		return res

	def DFS(self, dp, N, steps, x, y):
		if x >= N or x < 0 or y >= N or (y < 0):
			return 0
		if dp[x][y][steps] != -1:
			return dp[x][y][steps]
		cnt = 0
		dx = [-2, -2, -1, -1, 1, 1, 2, 2]
		dy = [-1, 1, -2, 2, -2, 2, -1, 1]
		for i in range(8):
			xx = x + dx[i]
			yy = y + dy[i]
			cnt += self.DFS(dp, N, steps - 1, xx, yy)
		dp[x][y][steps] = cnt
		return cnt


class Solution:

	def prob(self, i, j, s, N):
		pij = 0
		prev = [(i - 2, j - 1), (i - 2, j + 1), (i - 1, j - 2), (i - 1, j + 2), (i + 1, j - 2), (i + 1, j + 2), (i + 2, j - 1), (i + 2, j + 1)]
		for (ii, jj) in prev:
			pij += self.dp[ii][jj][s - 1] if 0 <= ii < N and 0 <= jj < N else 0
		return pij / 8

	def findProb(self, N, start_x, start_y, steps):
		self.dp = [[[0] * (steps + 1) for j in range(N)] for i in range(N)]
		self.dp[start_x][start_y][0] = 1
		for s in range(1, steps + 1):
			for i in range(N):
				for j in range(N):
					self.dp[i][j][s] = self.prob(i, j, s, N)
		p = 0
		for i in range(N):
			for j in range(N):
				p += self.dp[i][j][steps]
		return p


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dx = [-2, -1, +1, +2, +2, +1, -1, -2]
		dy = [+1, +2, +2, +1, -1, -2, -2, -1]
		dp = [[[0] * (steps + 1) for j in range(N)] for i in range(N)]
		for i in range(N):
			for j in range(N):
				dp[i][j][0] = 1
		for step in range(1, steps + 1):
			for x in range(N):
				for y in range(N):
					dp[x][y][step] = 0
					for i in range(8):
						newx = x + dx[i]
						newy = y + dy[i]
						if newx >= 0 and newx < N and (newy >= 0) and (newy < N):
							dp[x][y][step] += dp[newx][newy][step - 1] / 8.0
		return dp[start_x][start_y][steps]


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		n = N
		k = steps
		dic = {}
		c = 0
		for x in range(n):
			for y in range(n):
				dic[x, y] = c
				c += 1
		vis = {}
		for j in range(c + 1):
			vis[j] = [-1] * (k + 1)

		def fun(x, y, c):
			if c == 0:
				return 1
			else:
				s = 0
				if x - 1 >= 0 and y - 2 >= 0:
					ele = dic[x - 1, y - 2]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x - 1, y - 2, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x - 2 >= 0 and y - 1 >= 0:
					ele = dic[x - 2, y - 1]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x - 2, y - 1, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x - 2 >= 0 and y + 1 < n:
					ele = dic[x - 2, y + 1]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x - 2, y + 1, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x - 1 >= 0 and y + 2 < n:
					ele = dic[x - 1, y + 2]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x - 1, y + 2, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x + 1 < n and y + 2 < n:
					ele = dic[x + 1, y + 2]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x + 1, y + 2, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x + 2 < n and y + 1 < n:
					ele = dic[x + 2, y + 1]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x + 2, y + 1, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x + 2 < n and y - 1 >= 0:
					ele = dic[x + 2, y - 1]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x + 2, y - 1, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				if x + 1 < n and y - 2 >= 0:
					ele = dic[x + 1, y - 2]
					if vis[ele][c - 1] != -1:
						s += vis[ele][c - 1] * 0.125
					else:
						a = fun(x + 1, y - 2, c - 1)
						vis[ele][c - 1] = a
						s += a * 0.125
				return s
		ans = fun(start_x, start_y, steps)
		return ans


dct = {}

class Solution:

	def findProb(self, N, start_x, start_y, steps):
		tab = [[[0 for blabla in range(N)] for blablabla in range(N)] for bla in range(steps + 1)]
		moves = [[2, -1], [2, 1], [-2, -1], [-2, 1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
		for step in range(steps + 1):
			for x in range(N):
				for y in range(N):
					for move in moves:
						if step == 0:
							tab[step][x][y] = 1
						else:
							(new_x, new_y) = (x - move[0], y - move[1])
							if 0 <= new_x < N and 0 <= new_y < N:
								tab[step][x][y] += tab[step - 1][new_x][new_y] / 8
		return tab[steps][start_x][start_y]


from functools import lru_cache

class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dx = [1, 2, 2, 1, -1, -2, -2, -1]
		dy = [2, 1, -1, -2, -2, -1, 1, 2]

		def inside(x, y):
			return x >= 0 and x < N and (y >= 0) and (y < N)
		dp = [[[0] * (steps + 1) for ele in range(N)] for m in range(N)]
		for i in range(N):
			for j in range(N):
				dp[i][j][0] = 1
		for step in range(1, steps + 1):
			for x in range(N):
				for y in range(N):
					prob = 0.0
					for i in range(8):
						nx = x + dx[i]
						ny = y + dy[i]
						if inside(nx, ny):
							prob += dp[nx][ny][step - 1] / 8.0
					dp[x][y][step] = prob
		return dp[start_x][start_y][steps]

	def findProb_ok(self, n, x, y, steps):
		m = (n - 1) // 2

		@lru_cache(None)
		def helper2(x, y, total):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if total == 0:
				return 1
			if x > m:
				x = n - 1 - x
			if y > m:
				y = n - 1 - y
			res = 0
			for (dx, dy) in [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]:
				res += helper2(x + dx, y + dy, total - 1)
			return res
		return helper2(x, y, steps) / 8 ** steps

	def findProb2(self, n, x, y, steps):

		@lru_cache(None)
		def helper(x, y, total):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if total == 0:
				return 1
			res = 0
			for (addX, addY) in [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]:
				res += helper(x + addX, y + addY, total - 1)
			return res
		return helper(x, y, steps) / 8 ** steps


from functools import lru_cache

class Solution:

	def findProb(self, n, x, y, steps):
		m = (n - 1) // 2

		@lru_cache(None)
		def helper2(x, y, total):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if total == 0:
				return 1
			if x > m:
				x = n - 1 - x
			if y > m:
				y = n - 1 - y
			res = 0
			for (dx, dy) in [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]:
				res += helper2(x + dx, y + dy, total - 1)
			return res
		return helper2(x, y, steps) / 8 ** steps

	def findProb2(self, n, x, y, steps):

		@lru_cache(None)
		def helper(x, y, total):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if total == 0:
				return 1
			res = 0
			for (addX, addY) in [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]:
				res += helper(x + addX, y + addY, total - 1)
			return res
		return helper(x, y, steps) / 8 ** steps


from functools import lru_cache

class Solution:

	def findProb(self, n, r, c, k):

		@lru_cache(None)
		def helper(x, y, total):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if total == 0:
				return 1
			res = 0
			for (addX, addY) in [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]:
				res += helper(x + addX, y + addY, total - 1)
			return res
		return helper(r, c, k) / 8 ** k


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		prev = [[0 for i in range(N + 4)] for _ in range(N + 4)]
		curr = [[0 for i in range(N + 4)] for _ in range(N + 4)]
		for i in range(2, N + 2):
			for j in range(2, N + 2):
				prev[i][j] = 1
		for k in range(1, steps + 1):
			for i in range(2, N + 2):
				for j in range(2, N + 2):
					ans = 0
					ans += prev[i + 1][j - 2]
					ans += prev[i + 1][j + 2]
					ans += prev[i + 2][j - 1]
					ans += prev[i + 2][j + 1]
					ans += prev[i - 2][j - 1]
					ans += prev[i - 2][j + 1]
					ans += prev[i - 1][j - 2]
					ans += prev[i - 1][j + 2]
					curr[i][j] = ans
			prev = [[k for k in l] for l in curr]
		return prev[start_x + 2][start_y + 2] / pow(8, steps)


class Solution:

	def findProb(self, N, start_x, start_y, steps):

		def fun(i, j, k, n, dp):
			if i < 0 or i > n - 1 or j < 0 or (j > n - 1):
				return 0
			if dp[k][i][j] != -1:
				return dp[k][i][j]
			if k == 0:
				return 1
			ans = 0
			ans += fun(i + 1, j - 2, k - 1, n, dp)
			ans += fun(i + 1, j + 2, k - 1, n, dp)
			ans += fun(i + 2, j - 1, k - 1, n, dp)
			ans += fun(i + 2, j + 1, k - 1, n, dp)
			ans += fun(i - 2, j - 1, k - 1, n, dp)
			ans += fun(i - 2, j + 1, k - 1, n, dp)
			ans += fun(i - 1, j - 2, k - 1, n, dp)
			ans += fun(i - 1, j + 2, k - 1, n, dp)
			dp[k][i][j] = ans
			return dp[k][i][j]
		dp = [[[-1 for i in range(N)] for _ in range(N)] for l in range(steps + 1)]
		return fun(start_x, start_y, steps, N, dp) / pow(8, steps)


def valid_move(n, x, y):
	return x >= 0 and x < n and (y >= 0) and (y < n)

def find_prob(n, init_x, init_y, k):
	if k == 0:
		return 1
	mx = [1, 2, 2, 1, -1, -2, -2, -1]
	my = [2, 1, -1, -2, -2, -1, 1, 2]
	dp = [[[0 for i in range(n + 64)] for j in range(n + 64)] for l in range(k + 64)]
	for i in range(n):
		for j in range(n):
			dp[i][j][0] = 1
	for s in range(1, k + 1):
		for x in range(n):
			for y in range(n):
				prob = 0.0
				for i in range(8):
					nx = x + mx[i]
					ny = y + my[i]
					if valid_move(n, nx, ny):
						prob += dp[nx][ny][s - 1] / 8.0
				dp[x][y][s] = prob
	return dp[init_x][init_y][k]

class Solution:

	def findProb(self, n, init_x, init_y, k):
		return find_prob(n, init_x, init_y, k)


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dir = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]
		present = [[0 for i in range(N)] for j in range(N)]
		next = [[0 for i in range(N)] for j in range(N)]
		present[start_x][start_y] = 1
		for steps in range(0, steps):
			for i in range(N):
				for j in range(N):
					if present[i][j] != 0:
						for change in dir:
							newi = i + change[0]
							newj = j + change[1]
							if newi >= 0 and newi < N and (newj >= 0) and (newj < N):
								next[newi][newj] += present[i][j] / 8
			present = next
			next = [[0 for i in range(N)] for j in range(N)]
		res = 0
		for i in range(N):
			for j in range(N):
				res += present[i][j]
		return res


class Solution:

	def findProb(self, N, start_x, start_y, steps):

		def issafe(r, c):
			if r >= 0 and r < N and (c >= 0) and (c < N):
				return True
			return False
		curr = [[0 for i in range(N)] for j in range(N)]
		nex = [[0 for i in range(N)] for j in range(N)]
		moves = [[2, 1], [2, -1], [-2, -1], [-2, 1], [1, 2], [-1, 2], [1, -2], [-1, -2]]
		curr[start_x][start_y] = 1
		for k in range(steps):
			for i in range(N):
				for j in range(N):
					ni = 0
					nj = 0
					if curr[i][j] != 0:
						for move in moves:
							ni = i + move[0]
							nj = j + move[1]
							if issafe(ni, nj):
								nex[ni][nj] += curr[i][j] / 8
					curr[i][j] = 0
			curr = nex
			nex = [[0 for i in range(N)] for j in range(N)]
		ans = 0
		for i in range(N):
			for j in range(N):
				ans += curr[i][j]
		return ans


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dp = [[0] * N for _ in range(N)]
		dp[start_x][start_y] = 1
		for _ in range(steps):
			dp2 = [[0] * N for _ in range(N)]
			for (start_x, row) in enumerate(dp):
				for (start_y, val) in enumerate(row):
					for (dr, dc) in ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)):
						if 0 <= start_x + dr < N and 0 <= start_y + dc < N:
							dp2[start_x + dr][start_y + dc] += val / 8.0
			dp = dp2
		return sum(map(sum, dp))


class Solution:

	def valid(self, ni, nj, n):
		if ni < 0 or nj < 0 or nj >= n or (ni >= n):
			return False
		return True

	def findProb(self, N, start_x, start_y, k):
		c = [[0 for i in range(N)] for j in range(N)]
		n = [[0 for i in range(N)] for j in range(N)]
		c[start_x][start_y] = 1
		for m in range(1, k + 1):
			for i in range(N):
				for j in range(N):
					if c[i][j] != 0:
						ni = i + 2
						nj = j - 1
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i + 2
						nj = j + 1
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i - 2
						nj = j - 1
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i - 2
						nj = j + 1
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i + 1
						nj = j - 2
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i + 1
						nj = j + 2
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i - 1
						nj = j + 2
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
						ni = i - 1
						nj = j - 2
						if self.valid(ni, nj, N):
							n[ni][nj] += c[i][j] / 8
			c = [[n[i][j] for i in range(N)] for j in range(N)]
			n = [[0 for i in range(N)] for i in range(N)]
		s = 0
		for i in range(N):
			for j in range(N):
				s += c[i][j]
		return s


from functools import lru_cache

class Solution:

	def findProb(self, N, sx, sy, k):
		d = [(-2, -1), (1, 2), (-2, 1), (2, -1), (-1, 2), (2, 1), (1, -2), (-1, -2)]

		@lru_cache(None)
		def pseudo(xc, yc, s):
			if xc < 0 or xc >= N or yc < 0 or (yc >= N):
				return 0
			if not s:
				return 1
			answ = 0
			for (a, b) in d:
				answ = answ + pseudo(xc + a, yc + b, s - 1)
			return answ
		denominator = 8 ** k
		return pseudo(sx, sy, k) / denominator


from functools import lru_cache

class Solution:

	def findProb(self, n, sx, sy, k):
		d = [(-2, -1), (1, 2), (-2, 1), (2, -1), (-1, 2), (2, 1), (1, -2), (-1, -2)]

		@lru_cache(None)
		def helper(x, y, l):
			if x < 0 or x >= n or y < 0 or (y >= n):
				return 0
			if l == 0:
				return 1
			ans = 0
			for (a, b) in d:
				ans = ans + helper(x + a, y + b, l - 1)
			return ans
		total = 8 ** k
		return helper(sx, sy, k) / total


from functools import lru_cache

class Solution:

	def findProb(self, n, x, y, k):
		d = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

		@lru_cache(None)
		def solve(x, y, z):
			if not (0 <= x and x < n and (0 <= y) and (y < n)):
				return 0
			if z == 0:
				return 1
			ans = 0
			for (i, j) in d:
				ans += solve(x + i, y + j, z - 1)
			return ans
		return solve(x, y, k) / 8 ** k


from functools import lru_cache

class Solution:

	def findProb(self, n, x, y, steps):
		di = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

		@lru_cache(None)
		def solve(x, y, temp):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if temp == 0:
				return 1
			answer = 0
			for (i, j) in di:
				answer += solve(x + i, y + j, temp - 1)
			return answer
		return solve(x, y, steps) / 8 ** steps


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		if steps == 0:
			return 1
		dx = [1, 1, -1, -1, 2, 2, -2, -2]
		dy = [2, -2, 2, -2, 1, -1, 1, -1]
		dp = [[[0 for i in range(steps + 1)] for j in range(N)] for k in range(N)]
		for i in range(N):
			for j in range(N):
				dp[i][j][0] = 1
		for i in range(1, steps + 1):
			for j in range(N):
				for k in range(N):
					prob = 0
					for l in range(8):
						nx = j + dx[l]
						ny = k + dy[l]
						if nx >= 0 and nx < N and (ny >= 0) and (ny < N):
							prob += dp[nx][ny][i - 1] / 8
					dp[j][k][i] = prob
		return dp[start_x][start_y][steps]


class Solution:

	def findProb(self, N, X, Y, K):
		self.N = N
		self.IncX = [+2, +2, +1, +1, -1, -1, -2, -2]
		self.IncY = [+1, -1, +2, -2, +2, -2, +1, -1]
		next = [[1] * N] * N
		for i in range(1, K + 1):
			current = next
			next = [[0] * N for r in range(N)]
			for x in range(N):
				for y in range(N):
					for d in range(8):
						next[x][y] += self.getCurrent(current, x, y, d)
					next[x][y] /= 8.0
		return next[X][Y]

	def getCurrent(self, current, x, y, d):
		(nx, ny) = (x + self.IncX[d], y + self.IncY[d])
		if nx < 0 or N <= nx:
			return 0.0
		if ny < 0 or N <= ny:
			return 0.0
		return current[nx][ny]


import collections

class Solution:

	def findProb(self, n, r, c, k):
		dp = collections.defaultdict(float)

		def dfs(r, c, k):
			nonlocal n
			if r < 0 or r >= n or c < 0 or (c >= n):
				return 0
			if k == 0:
				return 1
			for (tr, tc) in [(r, c), (c, r), (n - 1 - r, c), (n - 1 - c, r), (r, n - 1 - c), (c, n - 1 - r), (n - 1 - c, n - 1 - r), (n - 1 - r, n - 1 - c)]:
				if (tr, tc, k) in dp:
					return dp[tr, tc, k]
			res = 0
			for (nr, nc) in [(r - 2, c - 1), (r - 2, c + 1), (r - 1, c + 2), (r - 1, c - 2), (r + 1, c + 2), (r + 1, c - 2), (r + 2, c - 1), (r + 2, c + 1)]:
				res += dfs(nr, nc, k - 1)
			res /= 8
			dp[r, c, k] = res
			return res
		return dfs(r, c, k)


def find(rMax, cMax, x, y, steps, u):
	if steps == 0:
		return 1
	if u[x][y][steps] != -1:
		return u[x][y][steps]
	c = 0
	if x + 1 < rMax and y + 2 < cMax:
		c += find(rMax, cMax, x + 1, y + 2, steps - 1, u)
	if x + 1 < rMax and y - 2 >= 0:
		c += find(rMax, cMax, x + 1, y - 2, steps - 1, u)
	if x - 1 >= 0 and y + 2 < cMax:
		c += find(rMax, cMax, x - 1, y + 2, steps - 1, u)
	if x - 1 >= 0 and y - 2 >= 0:
		c += find(rMax, cMax, x - 1, y - 2, steps - 1, u)
	if x + 2 < rMax and y + 1 < cMax:
		c += find(rMax, cMax, x + 2, y + 1, steps - 1, u)
	if x + 2 < rMax and y - 1 >= 0:
		c += find(rMax, cMax, x + 2, y - 1, steps - 1, u)
	if x - 2 >= 0 and y + 1 < cMax:
		c += find(rMax, cMax, x - 2, y + 1, steps - 1, u)
	if x - 2 >= 0 and y - 1 >= 0:
		c += find(rMax, cMax, x - 2, y - 1, steps - 1, u)
	u[x][y][steps] = c
	return c

class Solution:

	def findProb(self, N, start_x, start_y, steps):
		u = [[[-1 for _ in range(steps + 1)] for _ in range(N)] for _ in range(N)]
		val = find(N, N, start_x, start_y, steps, u)
		v1 = 1
		for i in range(steps):
			v1 *= 8
		return val / v1


from functools import lru_cache

class Solution:

	def findProb(self, N, start_x, start_y, steps):
		d = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

		@lru_cache(None)
		def valid(x, y, K):
			if not (0 <= x < N and 0 <= y < N):
				return 0
			if K == 0:
				return 1
			outcome = 0
			for (i, j) in d:
				outcome += valid(x + i, y + j, K - 1)
			return outcome
		return valid(start_x, start_y, steps) / 8 ** steps


class Solution:

	def isValid(self, x, y, n):
		if x >= 0 and y >= 0 and (x < N) and (y < N):
			return True
		return False

	def findProb(self, N, start_x, start_y, steps):
		curr_ = [[0 for _ in range(N)] for _ in range(N)]
		next_ = [[0 for _ in range(N)] for _ in range(N)]
		curr_[start_x][start_y] = 1
		for k in range(steps):
			for i in range(N):
				for j in range(N):
					if curr_[i][j] != 0:
						a = i + 2
						b = j - 1
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i + 2
						b = j + 1
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i - 2
						b = j - 1
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i - 2
						b = j + 1
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i + 1
						b = j - 2
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i + 1
						b = j + 2
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i - 1
						b = j - 2
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
						a = i - 1
						b = j + 2
						if self.isValid(a, b, N):
							next_[a][b] += curr_[i][j] / 8
			curr_ = next_
			next_ = [[0 for _ in range(N)] for _ in range(N)]
		ans = 0
		for i in range(N):
			for j in range(N):
				ans += curr_[i][j]
		return ans


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		dx = [1, 2, 2, 1, -1, -2, -2, -1]
		dy = [2, 1, -1, -2, -2, -1, 1, 2]

		def inside(x, y):
			return x >= 0 and x < N and (y >= 0) and (y < N)
		dp = [[[0] * (steps + 1) for ele in range(N)] for m in range(N)]
		for i in range(N):
			for j in range(N):
				dp[i][j][0] = 1
		for step in range(1, steps + 1):
			for x in range(N):
				for y in range(N):
					prob = 0.0
					for i in range(8):
						nx = x + dx[i]
						ny = y + dy[i]
						if inside(nx, ny):
							prob += dp[nx][ny][step - 1] / 8.0
					dp[x][y][step] = prob
		return dp[start_x][start_y][steps]


class Solution:

	def findProb(self, N, r, c, K):
		dp = [[0] * N for _ in range(N)]
		dp[r][c] = 1
		for _ in range(K):
			dp2 = [[0] * N for _ in range(N)]
			for (r, row) in enumerate(dp):
				for (c, val) in enumerate(row):
					for (dr, dc) in ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)):
						if 0 <= r + dr < N and 0 <= c + dc < N:
							dp2[r + dr][c + dc] += val / 8.0
			dp = dp2
		return sum(map(sum, dp))


class Solution:

	def findProb(self, N, start_x, start_y, steps):
		cur = [[0 for j in range(N)] for i in range(N)]
		nex = [[0 for j in range(N)] for i in range(N)]
		cur[start_x][start_y] = 1
		px = [1, 1, -1, -1, 2, -2, 2, -2]
		py = [2, -2, 2, -2, 1, 1, -1, -1]

		def valid(dx, dy, N):
			if (dx >= 0 and dx < N) and (dy >= 0 and dy < N):
				return True
			else:
				return False
		for m in range(steps):
			for i in range(N):
				for j in range(N):
					if cur[i][j] != 0:
						x = 0
						y = 0
						for k in range(8):
							dx = i + px[k]
							dy = j + py[k]
							if valid(dx, dy, N):
								nex[dx][dy] += cur[i][j] / 8
			cur = nex
			nex = [[0 for j in range(N)] for i in range(N)]
		su = 0
		for i in range(N):
			for j in range(N):
				su = su + cur[i][j]
		return su


class Solution:

	def findProb(self, n, r, c, k):

		def getvalid(cr, cc, n):
			child = []
			direction = [[2, 1], [-2, 1], [-1, 2], [1, 2], [2, -1], [-2, -1], [-1, -2], [1, -2]]
			for di in direction:
				crow = cr + di[0]
				ccol = cc + di[1]
				if 0 <= crow < n and 0 <= ccol < n:
					child.append((crow, ccol))
			return child
		prob = 1 / 8
		memo = [[0 for j in range(n)] for i in range(n)]
		memo[r][c] = 1
		for i in range(k):
			newmemo = [[0 for j in range(n)] for i in range(n)]
			for cr in range(n):
				for cc in range(n):
					for children in getvalid(cr, cc, n):
						newmemo[children[0]][children[1]] += memo[cr][cc] * prob
			memo = newmemo
		final = 0
		for row in memo:
			final += sum(row)
		return final


from functools import lru_cache

class Solution:

	def findProb(self, n, x, y, steps) -> float:
		ans = 0.0
		dirs = [(-1, -2), (-1, 2), (1, -2), (1, 2), (-2, 1), (-2, -1), (2, -1), (2, 1)]

		@lru_cache(None)
		def helper(x, y, k):
			if not (0 <= x < n and 0 <= y < n):
				return 0
			if k == 0:
				return 1
			count = 0
			for (i, j) in dirs:
				count += helper(x + i, y + j, k - 1)
			return count
		return helper(x, y, steps) / 8 ** steps


class Solution:

	def getProb(self, x, y, N, dp, s):
		dx = [1, 2, 2, 1, -1, -2, -2, -1]
		dy = [2, 1, -1, -2, -2, -1, 1, 2]
		prob = 0.0
		for i in range(8):
			nx = x + dx[i]
			ny = y + dy[i]
			if self.inside(nx, ny, N):
				prob += dp[s - 1][nx][ny] / 8.0
		return prob

	def inside(self, x, y, N):
		return x >= 0 and x < N and (y >= 0) and (y < N)

	def findProb(self, N, start_x, start_y, steps):
		if start_x < 0 or start_x >= N or start_y < 0 or (start_y >= N):
			return 0
		dp = [[[0] * N for _ in range(N)] for _ in range(steps + 1)]
		for i in range(N):
			for j in range(N):
				dp[0][i][j] = 1
		for s in range(1, steps + 1):
			for x in range(N):
				for y in range(N):
					dp[s][x][y] = self.getProb(x, y, N, dp, s)
		return dp[steps][start_x][start_y]


class Solution:
	dirs = [[1, 2], [-1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, 1], [-2, -1]]

	def on_board(self, i, j, N):
		return 0 <= i < N and 0 <= j < N

	def findProb(self, N, start_x, start_y, steps):
		probs = [[[0 for i in range(N)] for j in range(N)] for k in range(steps + 1)]
		probs[0][start_y][start_x] = 1
		for k in range(steps):
			for i in range(N):
				for j in range(N):
					if probs[k][i][j] != 0:
						for d in self.dirs:
							if self.on_board(i + d[0], j + d[1], N):
								probs[k + 1][i + d[0]][j + d[1]] += probs[k][i][j] / 8
		total_prob = 0
		for i in range(N):
			for j in range(N):
				total_prob += probs[-1][i][j]
		return total_prob