Knight’s tour for maximum points
Given a starting position in a 2D matrix representing a grid of points, the task is to find the minimum number of steps required for a knight to collect the maximum points, subject to the following conditions:
- The knight can move only as per the rules of a standard chess knight (i.e. two squares in one direction and one square in a perpendicular direction).
- The knight can collect all the points from all the cells that can be visited in exactly i steps without revisiting any cell.
- 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.
- The knight can start and end at any cell on the grid.
- The grid can have any number of rows and columns.
Note: The knight moves exactly the same as the knight on a chess board. Please follow 0-based indexing.
Examples:
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.
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
Approach: To solve the problem follow the below idea:
The idea is to to explore all the valid neighboring cells from the current cell using BFS traversal, and keep track of the visited cells. Now, calculate the total points collected by the knight, and add the points to a list at each level. After the BFS completes, find the maximum sum of points that can be collected and return the level at which the maximum sum is collected.
Below are the steps for the above approach:
- Create a 2d visited array of size n*m to keep track of visited cells.
- Mark starting position as true.
- visited[start_x][start_y] = true.
- Create a queue to perform BFS traversal and push the starting position in the queue.
- Create a list to store the sum of points collected at each level of the BFS traversal
- While the queue is not empty run a loop.
- Initialize a variable say size and store the size of the current level by getting the size of the queue.
- Initialize a variable_points = 0 for the current level.
- Run a loop to process all the cells at the current level.
- Dequeue the front element of the queue and store its x and y coordinates.
- Add the points at the current cell to the total points collected, points += arr[x][y].
- Visit all the neighboring cells that are valid and have not been visited before.
- Store the new x and y coordinates of the neighboring cell using the dx and dy arrays and check if it is valid and has not been visited before, mark it as visited, and add it to the queue.
- Add the sum of points collected at the current level to the list.
- Run a loop from the size of the back side of the point array, list[i] = x, which means we can get x points in the ith step. And do list[i] += list[i + list[i]].
- Find the max of the list[i] and return the answer.
Below is the code for the above approach:
C++
#include <iostream> #include <vector> #include <queue> using namespace std; // Method to check if the // given cell is valid bool isSafe( int i, int j, int n, int m) { return i > -1 && i < n && j > -1 && j < m; } int dx[] = { -2, -1, 1, 2, 2, 1, -1, -2 }; int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; // Method to find the maximum sum of // points that can be collected by a // knight starting from (start_x, // start_y) and moving according // to the given movements int knightTravel(vector<vector< int >>& arr, int start_x, int start_y) { int n = arr.size(); int m = arr[0].size(); // Create a boolean array to keep // track of visited cells vector<vector< bool >> visited(n, vector< bool >(m, false )); visited[start_x][start_y] = true ; // Create a queue to perform // BFS traversal queue<vector< int >> q; q.push({ start_x, start_y }); // Create a list to store the sum // of points collected at each // level of the BFS traversal vector< int > list; int points = 0; // Perform BFS traversal while (!q.empty()) { int size = q.size(); points = 0; // Process all the cells at // the current level for ( int i = 0; i < size; i++) { vector< int > temp = q.front(); q.pop(); int x = temp[0], y = temp[1]; // Add the points at the // current cell to the // total points collected points += arr[x][y]; // Visit all the neighboring // cells that are valid // and have not been // visited before for ( int k = 0; k < 8; k++) { int xi = x + dx[k]; int xj = y + dy[k]; if (isSafe(xi, xj, n, m) && !visited[xi][xj]) { visited[xi][xj] = true ; q.push({ xi, xj }); } } } // Add the sum of points // collected at the current // level to the list list.push_back(points); } // Find the maximum sum of points // that can be collected int max = -1, ans = -1; for ( int i = list.size() - 1; i > -1; i--) { if (list[i] + i < list.size()) list[i] += list[i + list[i]]; } for ( int i = 0; i < list.size(); i++) { if (list[i] > max) { max = list[i]; ans = i; } } // Return the level at which the // maximum sum of points // was collected return ans; } // Drivers code int main() { vector<vector< int >> 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 } }; int start_x = 4; int start_y = 5; // Function Call int result = knightTravel(arr, start_x, start_y); cout << result << endl; return 0; } |
Java
import java.util.*; public class Solution { // Method to find the maximum sum of // points that can be collected by a // knight starting from (start_x, // start_y) and moving according // to the given movements public static int knightTravel( int arr[][], int start_x, int start_y) { int n = arr.length; int m = arr[ 0 ].length; // Create a boolean array to keep // track of visited cells boolean visited[][] = new boolean [n][m]; visited[start_x][start_y] = true ; // Create a queue to perform // BFS traversal Queue< int []> q = new LinkedList<>(); q.add( new int [] { start_x, start_y }); // Create a list to store the sum // of points collected at each // level of the BFS traversal List<Integer> list = new ArrayList<>(); int points = 0 ; // Perform BFS traversal while (!q.isEmpty()) { int size = q.size(); points = 0 ; // Process all the cells at // the current level for ( int i = 0 ; i < size; i++) { int temp[] = q.poll(); int x = temp[ 0 ], y = temp[ 1 ]; // Add the points at the // current cell to the // total points collected points += arr[x][y]; // Visit all the neighboring // cells that are valid // and have not been // visited before for ( int k = 0 ; k < 8 ; k++) { int xi = x + dx[k]; int xj = y + dy[k]; if (isSafe(xi, xj, n, m) && !visited[xi][xj]) { visited[xi][xj] = true ; q.add( new int [] { xi, xj }); } } } // Add the sum of points // collected at the current // level to the list list.add(points); } // Find the maximum sum of points // that can be collected int max = - 1 , ans = - 1 ; for ( int i = list.size() - 1 ; i > - 1 ; i--) { if (list.get(i) + i < list.size()) list.set(i, list.get(i) + list.get(i + list.get(i))); } for ( int i = 0 ; i < list.size(); i++) { if (list.get(i) > max) { max = list.get(i); ans = i; } } // Return the level at which the // maximum sum of points // was collected return ans; } // Method to check if the // given cell is valid static boolean isSafe( int i, int j, int n, int m) { return i > - 1 && i < n && j > - 1 && j < m; } static int dx[] = { - 2 , - 1 , 1 , 2 , 2 , 1 , - 1 , - 2 }; static int dy[] = { 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 }; // Drivers code public static void main(String[] args) { int [][] 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 } }; int start_x = 4 ; int start_y = 5 ; // Function Call int result = knightTravel(arr, start_x, start_y); System.out.println(result); } } |
Python3
from typing import List from queue import Queue def knightTravel(arr: List [ List [ int ]], start_x: int , start_y: int ) - > int : n, m = len (arr), len (arr[ 0 ]) # Create a boolean array to keep # track of visited cells visited = [[ False ] * m for _ in range (n)] visited[start_x][start_y] = True # Create a queue to perform # BFS traversal q = Queue() q.put((start_x, start_y)) # Create a list to store the sum # of points collected at each # level of the BFS traversal level_sums = [] # Perform BFS traversal while not q.empty(): size = q.qsize() points = 0 # Process all the cells at # the current level for _ in range (size): x, y = q.get() # Add the points at the # current cell to the # total points collected points + = arr[x][y] # Visit all the neighboring # cells that are valid # and have not been # visited before for k in range ( 8 ): xi = x + dx[k] xj = y + dy[k] if isSafe(xi, xj, n, m) and not visited[xi][xj]: visited[xi][xj] = True q.put((xi, xj)) # Add the sum of points # collected at the current # level to the list level_sums.append(points) # Find the maximum sum of points # that can be collected max_sum = - 1 ans = - 1 for i in range ( len (level_sums) - 1 , - 1 , - 1 ): if level_sums[i] + i < len (level_sums): level_sums[i] + = level_sums[i + level_sums[i]] if level_sums[i] > max_sum: max_sum = level_sums[i] ans = i # Return the level at which the # maximum sum of points # was collected return ans # Method to check if the # given cell is valid def isSafe(i: int , j: int , n: int , m: int ) - > bool : return i > - 1 and i < n and j > - 1 and j < m dx = [ - 2 , - 1 , 1 , 2 , 2 , 1 , - 1 , - 2 ] dy = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ] # Driver code 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 ]] start_x = 4 start_y = 5 result = knightTravel(arr, start_x, start_y) print (result) |
C#
using System; using System.Collections.Generic; class Solution { // Method to find the maximum sum of // points that can be collected by a // knight starting from (start_x, // start_y) and moving according // to the given movements public static int KnightTravel( int [][] arr, int start_x, int start_y) { int n = arr.Length; int m = arr[0].Length; // Create a boolean array to keep // track of visited cells bool [,] visited = new bool [n, m]; visited[start_x, start_y] = true ; // Create a queue to perform BFS traversal Queue< int []> q = new Queue< int []>(); q.Enqueue( new int [] { start_x, start_y }); // Create a list to store the sum // of points collected at each // level of the BFS traversal List< int > list = new List< int >(); int points = 0; // Perform BFS traversal while (q.Count > 0) { int size = q.Count; points = 0; // Process all the cells at // the current level for ( int i = 0; i < size; i++) { int [] temp = q.Dequeue(); int x = temp[0], y = temp[1]; // Add the points at the // current cell to the // total points collected points += arr[x][y]; // Visit all the neighboring // cells that are valid // and have not been // visited before for ( int k = 0; k < 8; k++) { int xi = x + dx[k]; int xj = y + dy[k]; if (IsSafe(xi, xj, n, m) && !visited[xi, xj]) { visited[xi, xj] = true ; q.Enqueue( new int [] { xi, xj }); } } } // Add the sum of points // collected at the current // level to the list list.Add(points); } // Find the maximum sum of points // that can be collected int max = -1, ans = -1; for ( int i = list.Count - 1; i > -1; i--) { if (list[i] + i < list.Count) list[i] += list[i + list[i]]; } for ( int i = 0; i < list.Count; i++) { if (list[i] > max) { max = list[i]; ans = i; } } // Return the level at which the // maximum sum of points // was collected return ans; } // Method to check if the given cell is valid static bool IsSafe( int i, int j, int n, int m) { return i > -1 && i < n && j > -1 && j < m; } static int [] dx = { -2, -1, 1, 2, 2, 1, -1, -2 }; static int [] dy = { 1, 2, 2, 1, -1, -2, -2, -1 }; // Driver's code public static void Main( string [] args) { int [][] arr = { new int [] { 0, 0, 0, 2, 0, 2, 0, 2, 0, 0 }, new int [] { 0, 0, 2, 0, 2, 0, 2, 0, 2, 0 }, new int [] { 0, 2, 0, 0, 1, 2, 0, 0, 0, 2 }, new int [] { 0, 0, 2, 0, 2, 0, 2, 0, 2, 0 }, new int [] { 0, 2, 0, 2, 0, 0, 0, 2, 0, 2 }, new int [] { 0, 0, 2, 0, 2, 0, 2, 0, 2, 0 }, new int [] { 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 }, new int [] { 0, 0, 2, 0, 2, 0, 2, 0, 2, 0 }, new int [] { 0, 0, 0, 2, 0, 2, 0, 2, 0, 0 } }; int start_x = 4; int start_y = 5; // Function Call int result = KnightTravel(arr, start_x, start_y); Console.WriteLine(result); } } |
Javascript
const dx = [-2, -1, 1, 2, 2, 1, -1, -2]; const dy = [1, 2, 2, 1, -1, -2, -2, -1]; // Function to check if the given cell is within // the board boundaries function GFG(x, y, n, m) { return x >= 0 && x < n && y >= 0 && y < m; } // Function to find the maximum points collected by the knight function knightTravel(arr, start_x, start_y) { const n = arr.length; const m = arr[0].length; // Create a visited array to // keep track of visited cells const visited = Array.from({ length: n }, () => Array(m).fill( false )); visited[start_x][start_y] = true ; // Create a queue for BFS traversal const queue = []; queue.push([start_x, start_y]); // Create an array to store points collected at each level const pointsList = []; let points = 0; // Perform BFS traversal while (queue.length > 0) { const levelSize = queue.length; points = 0; // Process all cells at the current level for (let i = 0; i < levelSize; i++) { const [x, y] = queue.shift(); // Add the points at the current cell to // the total points collected points += arr[x][y]; // Visit all neighboring cells that are valid and unvisited for (let k = 0; k < 8; k++) { const xi = x + dx[k]; const yi = y + dy[k]; if (GFG(xi, yi, n, m) && !visited[xi][yi]) { visited[xi][yi] = true ; queue.push([xi, yi]); } } } // Add the sum of points collected at // the current level to the list pointsList.push(points); } // Find the maximum sum of points collected let max = -1; let ans = -1; for (let i = pointsList.length - 1; i >= 0; i--) { if (pointsList[i] + i < pointsList.length) { pointsList[i] += pointsList[i + pointsList[i]]; } } for (let i = 0; i < pointsList.length; i++) { if (pointsList[i] > max) { max = pointsList[i]; ans = i; } } // Return the level at which the // maximum points were collected return ans; } // Sample input const 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] ]; const start_x = 4; const start_y = 5; // Function Call const result = knightTravel(arr, start_x, start_y); console.log(result); |
1
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Related Articles:
Contact Us