Knight is at (start_x,start_y) in Geekland which is represented by an NxM 2D matrix.
Each cell in the matrix contains some points. In the ith step, the knight can collect all the points from all the cells that can be visited in exactly i steps without revisiting any cell.
Also, the knight has some magical powers that enable him to fetch coins from the future i.e. If the knight can collect y coins in the xth step he can fetch all the coins that he will collect in the (x + y)th step and if the knight can collect z coins in the yth step he can fetch all the coins that he will collect in the (y + z)th step and so on without increasing the step count i.e. knight will stay on xth step and will get all the coins of the future steps mentioned above((x + y)th step coins + (y+z)th steps + ...).
Find the minimum number of steps required to collect the maximum points.
Note: The knight moves exactly the same as the knight on a chess board. Please follow 0 indexing.
Example 1:
Input:
n = 9
m = 10
start_x = 4, start_y = 5
arr =
0 0 0 2 0 2 0 2 0 0
0 0 2 0 2 0 2 0 2 0
0 2 0 0 1 2 0 0 0 2
0 0 2 0 2 0 2 0 2 0
0 2 0 2 0 0 0 2 0 2
0 0 2 0 2 0 2 0 2 0
0 2 0 0 0 2 0 0 0 2
0 0 2 0 2 0 2 0 2 0
0 0 0 2 0 2 0 2 0 0
Output: 1
Explanation: minimum knight have to take 1 steps to gain maximum points.
Initially, the knight has 0 coins, he will take 1 step to collect 1 point (sum of cells denoted in red color).
Now in the second step, he can collect points from all the cells colored green i.e. 64 points.
But with his magical power, at the 1st step, he can fetch points from the (1 + 1)th step. Therefore he can collect 1 + 64 coins at step 1 only. Hence answer is 1.
Example 2:
Input:
n = 3 
m = 3
start_x = 2, start_y = 1
arr =
7 6 8
9 1 4
6 2 8
Output:0
Explanation:
Initially, the knight has 2 points, or more formally we can say that at the 0th step knight has 2 points.
In the first step, he can collect points from cells (0, 0) and (0, 2) i.e. 15 points.
In the second step, he can collect points from cells (1, 0) and (1, 2) i.e. 13 coins.
In the third step, he can collect points from cells (2, 0) and (2, 2) i.e. 14 points.
In the fourth step, he can collect points from the cell (0, 1) i.e. 6 points.
So in each step, he can collect coins like -You can see in the below image  Knight can collect 15 coins in the 0th step only
Your Task:
You don't need to read input or print anything. Your task is to complete the function knightInGeekland() which takes 2-d array arr[][], starting coordinates of knight start_x, and start_y as input, and return an integer value as min steps to gain max points.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
   1 <= len(arr), len(arr[0]) < 10^{3}
   0 <= values in arr <=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def knightInGeekland(self, arr, start):

        pass

    

Solutions:
class Solution:

	def knightInGeekland(self, arr, start):
		(m, n) = (len(arr), len(arr[0]))
		q = [(start[0], start[1])]
		coins = []
		visited = {(start[0], start[1])}
		ds = [(r, c) for r in (-2, 2) for c in (-1, 1)] + [(r, c) for r in (-1, 1) for c in (-2, 2)]
		while q:
			s = 0
			nq = []
			for (r0, c0) in q:
				s += arr[r0][c0]
				for (dr, dc) in ds:
					(r, c) = (r0 + dr, c0 + dc)
					if (r, c) not in visited and 0 <= r < m and (0 <= c < n):
						nq.append((r, c))
						visited.add((r, c))
			coins.append(s)
			q = nq
		cnt = 0
		ans = 0
		for i in range(len(coins) - 1, -1, -1):
			if coins[i] + i < len(coins):
				coins[i] += coins[coins[i] + i]
			if coins[i] >= cnt:
				cnt = coins[i]
				ans = i
		return ans


class Solution:

	def knightInGeekland(self, arr, start):
		x = [-2, -2, 2, 2, -1, 1, -1, 1]
		y = [-1, 1, -1, 1, -2, -2, 2, 2]
		n = len(arr)
		m = len(arr[0])
		visit = [[False for _ in range(m)] for _ in range(n)]
		data = []
		start = [start]
		visit[start[0][0]][start[0][1]] = True
		while start:
			count = 0
			for s in range(len(start)):
				count += arr[start[0][0]][start[0][1]]
				(prev_x, prev_y) = start[0]
				del start[0]
				for (i, j) in zip(x, y):
					next_i = prev_x + i
					next_j = prev_y + j
					if 0 <= next_i < n and 0 <= next_j < m and (visit[next_i][next_j] != True):
						start.append([next_i, next_j])
						visit[next_i][next_j] = True
			data.append(count)
		for i in range(len(data) - 1, -1, -1):
			try:
				data[i] += data[data[i] + i]
			except:
				pass
		return data.index(max(data))


class Solution:

	def knightInGeekland(self, arr, start):
		n = len(arr)
		m = len(arr[0])
		points = []
		seen = set([(start[0], start[1])])
		from collections import deque
		q = deque([start])
		while q:
			nq = []
			curpoints = 0
			for (x, y) in q:
				curpoints += arr[x][y]
				for (nx, ny) in [[x - 1, y - 2], [x - 2, y - 1], [x + 1, y + 2], [x + 2, y + 1], [x - 1, y + 2], [x - 2, y + 1], [x + 1, y - 2], [x + 2, y - 1]]:
					if 0 <= nx < n and 0 <= ny < m and ((nx, ny) not in seen):
						nq.append([nx, ny])
						seen.add((nx, ny))
			points.append(curpoints)
			q = nq
		mx = 0
		ret = 0
		for i in range(len(points) - 1, -1, -1):
			if points[i] + i < len(points):
				points[i] += points[points[i] + i]
			if points[i] >= mx:
				mx = points[i]
				ret = i
		return ret


from collections import deque

class Solution:

	def knightInGeekland(self, arr, start):
		n = len(arr)
		m = len(arr[0])
		vis = set()
		(x, y) = start
		q = deque([[x, y]])
		coins = []
		while q:
			cnt = 0
			q1 = deque()
			while q:
				(i, j) = q.popleft()
				if (i, j) in vis:
					continue
				vis.add((i, j))
				cnt += arr[i][j]
				for (x, y) in ((i - 2, j - 1), (i - 2, j + 1), (i - 1, j + 2), (i + 1, j + 2), (i + 2, j + 1), (i + 2, j - 1), (i + 1, j - 2), (i - 1, j - 2)):
					if 0 <= x < n and 0 <= y < m and ((x, y) not in vis):
						q1.append([x, y])
			coins.append(cnt)
			q = q1
		step = -1
		cnt = -1
		x = len(coins)
		for i in range(x - 1, -1, -1):
			c = coins[i]
			if i + c < x:
				coins[i] = coins[i + c] + c
			if cnt <= coins[i]:
				step = i
				cnt = coins[i]
		return step


class Solution:

	def knightInGeekland(self, arr, start):
		(n, m) = (len(arr), len(arr[0]))
		dp = [[-1 for _ in range(m)] for __ in range(n)]
		coins = []
		starting = [[start[0], start[1]]]
		coins.append(arr[start[0]][start[1]])
		dp[start[0]][start[1]] = 1
		self.traverse(starting, dp, arr, coins, 1)
		coin_dp = [0 for _ in range(len(coins))]
		for k in range(len(coin_dp)):
			self.max_ind(coins, coin_dp, k)
		maxi = 0
		for i in range(len(coin_dp)):
			if coin_dp[i] > coin_dp[maxi]:
				maxi = i
		return maxi

	def next_cell(self, row, col):
		next_ = [[row + 2, col + 1], [row + 2, col - 1], [row - 2, col + 1], [row - 2, col - 1], [row + 1, col + 2], [row + 1, col - 2], [row - 1, col + 2], [row - 1, col - 2]]
		return next_

	def valid_cells(self, input_cells, array, n, m):
		target_cell = []
		for item in input_cells:
			nxt = self.next_cell(item[0], item[1])
			for ele in nxt:
				if 0 <= ele[0] <= n - 1 and 0 <= ele[1] <= m - 1:
					if array[ele[0]][ele[1]] == -1:
						array[ele[0]][ele[1]] = 1
						target_cell.append([ele[0], ele[1]])
		return target_cell

	def traverse(self, cur, array, main, cnt, step):
		tgt = self.valid_cells(cur, array, len(main), len(main[0]))
		if cnt[step - 1] == 0:
			if len(tgt) == 0:
				return cnt
		temp = 0
		for cell in tgt:
			temp += main[cell[0]][cell[1]]
		cnt.append(temp)
		return self.traverse(tgt, array, main, cnt, step + 1)

	def max_ind(self, main, dp, ind):
		if dp[ind] == 0 and main[ind] != 0:
			if ind + main[ind] < len(main):
				dp[ind] = main[ind] + self.max_ind(main, dp, ind + main[ind])
			else:
				dp[ind] = main[ind]
		return dp[ind]


import queue
from collections import deque

class Solution:

	def knightInGeekland(self, arr, start):
		(n, m) = (len(arr), len(arr[0]))
		l = [[0 for i in range(m)] for i in range(n)]
		l[start[0]][start[1]] = 1
		q = deque()
		q.append(start)
		dx = [1, 1, -1, -1, 2, 2, -2, -2]
		dy = [2, -2, 2, -2, 1, -1, 1, -1]
		coin_id = []
		summax = 0
		while q:
			k = len(q)
			coins = 0
			while k:
				t = q.popleft()
				(x, y) = (t[0], t[1])
				coins += arr[x][y]
				for j in range(8):
					(newx, newy) = (x + dx[j], y + dy[j])
					if newx >= 0 and newy >= 0 and (newx < n) and (newy < m) and (l[newx][newy] == 0):
						q.append([newx, newy])
						l[newx][newy] = 1
				k -= 1
			coin_id.append(coins)
		ans = -1
		maxcoin = float('-inf')
		for i in range(len(coin_id) - 1, -1, -1):
			if i + coin_id[i] < len(coin_id):
				coin_id[i] += coin_id[i + coin_id[i]]
			if coin_id[i] >= maxcoin:
				ans = i
				maxcoin = coin_id[i]
		return ans


from collections import deque

class Solution:

	def knightInGeekland(self, arr, start):
		que = deque()
		que.append([start[0], start[1]])
		visited = [[False for i in range(len(arr[0]))] for i in range(len(arr))]
		visited[start[0]][start[1]] = True
		coins = []
		row = [-2, -2, -1, -1, 1, 1, 2, 2]
		col = [-1, 1, -2, 2, -2, 2, -1, 1]
		res = 0
		ans = 0
		while que:
			k = len(que)
			sumi = 0
			for j in range(k):
				curr = que.popleft()
				sumi += arr[curr[0]][curr[1]]
				for x in range(8):
					a = curr[0] + row[x]
					b = curr[1] + col[x]
					if a < len(arr) and b < len(arr[0]) and (a >= 0) and (b >= 0) and (visited[a][b] == False):
						que.append([a, b])
						visited[a][b] = True
			coins.append(sumi)
		dp = [-1 for i in range(len(coins))]

		def solve(i, dp, coins):
			if i >= len(coins):
				return 0
			if dp[i] != -1:
				return dp[i]
			if coins[i] == 0:
				return dp[i]
			dp[i] = coins[i] + solve(i + coins[i], dp, coins)
			return dp[i]
		for i in range(len(coins)):
			solve(i, dp, coins)
		for i in range(len(dp)):
			if res < dp[i]:
				ans = i
				res = dp[i]
		return ans