Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position.
Examples:
In above diagram Knight takes 3 step to reach
from (4, 5) to (1, 1) (4, 5) -> (5, 3) -> (3, 2)
-> (1, 1) as shown in diagram
This problem can be seen as shortest path in unweighted graph. Therefore we use BFS to solve this problem. We try all 8 possible positions where a Knight can reach from its position. If reachable position is not already visited and is inside the board, we push this state into queue with distance 1 more than its parent state. Finally we return distance of target position, when it gets pop out from queue.
Below code implements BFS for searching through cells, where each cell contains its coordinate and distance from starting node. In worst case, below code visits all cells of board, making worst-case time complexity as O(N^2)
C++
// C++ program to find minimum steps to reach to // specific cell in minimum moves by Knight #include <bits/stdc++.h> using namespace std; // structure for storing a cell's data struct cell { int x, y; int dis; cell() {} cell(int x, int y, int dis) : x(x), y(y), dis(dis) {} }; // Utility method returns true if (x, y) lies // inside Board bool isInside(int x, int y, int N) { if (x >= 1 && x <= N && y >= 1 && y <= N) return true; return false; } // Method returns minimum step to reach target position int minStepToReachTarget(int knightPos[], int targetPos[], int N) { // x and y direction, where a knight can move int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2}; int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; // queue for storing states of knight in board queue<cell> q; // push starting position of knight with 0 distance q.push(cell(knightPos[0], knightPos[1], 0)); cell t; int x, y; bool visit[N + 1][N + 1]; // make all cell unvisited for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) visit[i][j] = false; // visit starting state visit[knightPos[0]][knightPos[1]] = true; // loop untill we have one element in queue while (!q.empty()) { t = q.front(); q.pop(); // if current cell is equal to target cell, // return its distance if (t.x == targetPos[0] && t.y == targetPos[1]) return t.dis; // loop for all reachable states for (int i = 0; i < 8; i++) { x = t.x + dx[i]; y = t.y + dy[i]; // If reachable state is not yet visited and // inside board, push that state into queue if (isInside(x, y, N) && !visit[x][y]) { visit[x][y] = true; q.push(cell(x, y, t.dis + 1)); } } } } // Driver code to test above methods int main() { int N = 30; int knightPos[] = {1, 1}; int targetPos[] = {30, 30}; cout << minStepToReachTarget(knightPos, targetPos, N); return 0; } |
Java
import java.util.*; // Java program to find minimum steps to reach to // specific cell in minimum moves by Knight class GFG { // Class for storing a cell's data static class cell { int x, y; int dis; public cell(int x, int y, int dis) { this.x = x; this.y = y; this.dis = dis; } } // Utility method returns true if (x, y) lies // inside Board static boolean isInside(int x, int y, int N) { if (x >= 1 && x <= N && y >= 1 && y <= N) return true; return false; } // Method returns minimum step // to reach target position static int minStepToReachTarget(int knightPos[], int targetPos[], int N) { // x and y direction, where a knight can move int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2}; int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; // queue for storing states of knight in board Vector<cell> q = new Vector<>(); // push starting position of knight with 0 distance q.add(new cell(knightPos[0], knightPos[1], 0)); cell t ; int x, y; boolean visit[][] = new boolean[N + 1][N + 1]; // make all cell unvisited for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) visit[i][j] = false; // visit starting state visit[knightPos[0]][knightPos[1]] = true; // loop untill we have one element in queue while (!q.isEmpty()) { t = q.firstElement(); q.remove(0); // if current cell is equal to target cell, // return its distance if (t.x == targetPos[0] && t.y == targetPos[1]) return t.dis; // loop for all reachable states for (int i = 0; i < 8; i++) { x = t.x + dx[i]; y = t.y + dy[i]; // If reachable state is not yet visited and // inside board, push that state into queue if (isInside(x, y, N) && !visit[x][y]) { visit[x][y] = true; q.add(new cell(x, y, t.dis + 1)); } } } return Integer.MAX_VALUE; } // Driver code public static void main(String[] args) { int N = 30; int knightPos[] = {1, 1}; int targetPos[] = {30, 30}; System.out.println(minStepToReachTarget(knightPos, targetPos, N)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 code to find minimum steps to reach # to specific cell in minimum moves by Knight class cell: def __init__(self, x = 0, y = 0, dist = 0): self.x = x self.y = y self.dist = dist # checks whether given position is # inside the board def isInside(x, y, N): if (x >= 1 and x <= N and y >= 1 and y <= N): return True return False # Method returns minimum step to reach # target position def minStepToReachTarget(knightpos, targetpos, N): #all possible movments for the knight dx = [2, 2, -2, -2, 1, 1, -1, -1] dy = [1, -1, 1, -1, 2, -2, 2, -2] queue = [] # push starting position of knight # with 0 distance queue.append(cell(knightpos[0], knightpos[1], 0)) # make all cell unvisited visited = [[False for i in range(N + 1)] for j in range(N + 1)] # visit starting state visited[knightpos[0]][knightpos[1]] = True # loop untill we have one element in queue while(len(queue) > 0): t = queue[0] queue.pop(0) # if current cell is equal to target # cell, return its distance if(t.x == targetpos[0] and t.y == targetpos[1]): return t.dist # iterate for all reachable states for i in range(8): x = t.x + dx[i] y = t.y + dy[i] if(isInside(x, y, N) and not visited[x][y]): visited[x][y] = True queue.append(cell(x, y, t.dist + 1)) # Driver Code if __name__=='__main__': N = 30 knightpos = [1, 1] targetpos = [30, 30] print(minStepToReachTarget(knightpos, targetpos, N)) # This code is contributed by # Kaustav kumar Chanda |
Output:
20
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
1 Comments