Algorithm

Problem #3. (Programming) Knight (20 pts) Given a squared chess board, find the minimum number of steps taken by a Knight to reach desired destination from, its given source position. As illustrated in the right figure, Knight can move to 8 different locations by a single step. For instance, we need at least 3 steps to move the Knight at (2,4) to the goal position (6,1). Specifically, the Knight can move the following path: (2,4) (3,2) (4,0) (6,1). Note that, locations are represented by (vertical, horizontal) coordinates and left-upper corner is (0,0) similar to the array in C/C++ Your program is required to get an input from "input_knights.txt" and write the result to a file output knight.txt" as the following example: input knight.txt output knight.txt 2 4 6 1 The first value in the input file indicates the chess board size N (S S N S 15)The second and third lines are the source and destination locations, repsectively. The output file only contains the minimum number of steps from the source to the destination. You can output-1", if the destination is unreachable. Your program has to produce an answer within 5 seconds. You are asked to briefly describe your algorithm in the report and name your source code file "ID_Al Knight.epp