So, starting from the initial position we will try to make all 8 legal moves. ![]() Now, we have considered it as a graph, we can use the BFS algorithm to find the shortest path from square to square. The below image is showing how it will look if you consider the chessboard as a graph. Let’s imagine the chessboard as a graph where each square of the chessboard is a vertex and the edges can be one legal move of the knight. The problem asked us to find the least number of moves to move the knight from position to position. If you have played chess then you know that a knight moves two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). This problem can be solved by BFS(Breadth-First Search) algorithm. The minimum number of moves required for this is 3. Int E and int F: denotes the target of the KnightĮxample Input: A = 6, B = 6, C = 1, D = 1, E = 4, F = 5Įxplanation: The size of the chessboard is 6圆, the knight is initially at (1, 1) and the knight wants to reach position (4, 5). ![]() Int C and int D: denotes the position of the Knight
0 Comments
Leave a Reply. |