4.4

import java.io.*;
import java.util.*;

// Java program to find minimum steps to reach to
// specific cell in minimum moves by Knight
public class Main {

    // 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, int[][] Board)
    {
        if (x >= 1 && x <= N && y >= 1 && y <= N && Board[x-1][y-1] != -1)
            return true;
        return false;
    }

    // Method returns minimum step
    // to reach target position
    static int minStepToReachTarget(int[] knightPos,
                                    int[] targetPos, int N, int[][] Board)
    {
        // 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 = new LinkedList<>();

        // 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]; // default initialized to false

        // visit starting state
        visit[knightPos[0]][knightPos[1]] = true;

        // loop until we have one element in queue
        while (!q.isEmpty()) {
            t = q.poll();

            // 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, Board) && !visit[x][y]) {
                    visit[x][y] = true;
                    q.add(new cell(x, y, t.dis + 1));
                }
            }
        }
        return Integer.MAX_VALUE;
    }

    private static int chooseInputMethod() {
        int choice;
        boolean isCorrect;

        choice = -1;

        do {
            System.out.println("Choose an option:");
            System.out.println("1. Input data manually");
            System.out.println("2. Read data from a text file");
            isCorrect = true;
            try {
                Scanner scanner = new Scanner(System.in);
                choice = scanner.nextInt();
            } catch (NumberFormatException e) {
                System.out.println("Invalid input.");
                isCorrect = false;
            }

            if (isCorrect && !(choice == 1 || choice == 2)) {
                System.out.println("Error! You have to input either 1 or 2.");
                isCorrect = false;
            }
        } while (!isCorrect);
        return choice;
    }

    private static int[] inputStartPosManually(Scanner scanner) {
        System.out.println("Enter the starting position for the knight:");
        int[] knightPosition= {0, 0};
        boolean isCorrect;
        do {
            System.out.print("X1: ");
            isCorrect = true;
            try {
                knightPosition[0] = scanner.nextInt();
            } catch (Exception e) {
                System.out.println("Invalid input.");
                isCorrect = false;
                scanner.nextLine();
            }

            if (isCorrect && (knightPosition[0] < 1 || knightPosition[0] > 8)) {
                System.out.println("Please enter a value from " + 1 + " to " + 8 + "!");
                isCorrect = false;
            }
        } while (!isCorrect);

        do {
            System.out.print("Y1: ");
            isCorrect = true;
            try {
                knightPosition[1] = scanner.nextInt();
            } catch (Exception e) {
                System.out.println("Invalid input.");
                isCorrect = false;
                scanner.nextLine();
            }

            if (isCorrect && (knightPosition[1] < 1 || knightPosition[1] > 8)) {
                System.out.println("Please enter a value from " + 1 + " to " + 8 + "!");
                isCorrect = false;
            }
        } while (!isCorrect);

        return knightPosition;

    }

    private static int[] inputTargetPosManually(Scanner scanner) {
        System.out.println("Enter the target position for the knight:");
        int[] targetPosition= {0, 0};
        boolean isCorrect;
        do {
            System.out.print("X2: ");
            isCorrect = true;
            try {
                targetPosition[0] = scanner.nextInt();
            } catch (Exception e) {
                System.out.println("Invalid input.");
                isCorrect = false;
                scanner.nextLine();
            }

            if (isCorrect && (targetPosition[0] < 1 || targetPosition[0] > 8)) {
                System.out.println("Please enter a value from " + 1 + " to " + 8 + "!");
                isCorrect = false;
            }
        } while (!isCorrect);

        do {
            System.out.print("Y2: ");
            isCorrect = true;
            try {
                targetPosition[1] = scanner.nextInt();
            } catch (Exception e) {
                System.out.println("Invalid input.");
                isCorrect = false;
                scanner.nextLine();
            }

            if (isCorrect && (targetPosition[1] < 1 || targetPosition[1] > 8)) {
                System.out.println("Please enter a value from " + 1 + " to " + 8 + "!");
                isCorrect = false;
            }
        } while (!isCorrect);

        return targetPosition;

    }
    private static String findFile(Scanner scanner) {
        String filePath;
        boolean isCorrect;
        do {
            isCorrect = true;
            System.out.print("Enter path to the file: ");
            filePath = scanner.nextLine();
            File file = new File(filePath);
            if (!file.exists()) {
                isCorrect = false;
                System.out.println("File not found at the specified path.");
            } else if (!filePath.endsWith(".txt")) {
                isCorrect = false;
                System.out.println("Error, wrong file type! File should have .txt extension.");
            }
        } while (!isCorrect);
        System.out.println("File found.");
        return filePath;
    }
    private static int[][] inputDataFromFile(String path) {
        int[][] Board = new int[8][8];

        try (Scanner fileScanner = new Scanner(new File(path))) {
            System.out.println("Reading file...");

            for (int i = 0; i < 8; i++){

                String line = fileScanner.nextLine();
                String[] parts = line.split(" ");

                for (int j = 0; j < 8; j++){
                    Board[i][j] = Integer.parseInt(parts[j]);
                }
            }
        } catch (IOException e) {
            System.out.println("Error reading file!");
        }

        return Board;
    }

    public static  int[][] AddPawns(Scanner scanner){
        int[][] ChessBoard = new int[8][8];
        int x = 0, y = 0;
        boolean isCorrect;
        int pawnNum = 0;

        do {
            System.out.println("Input the number of pawns you want to add to the chessboard: ");
            isCorrect = true;
            try {
                pawnNum = scanner.nextInt();
            } catch (NumberFormatException e) {
                System.out.println("Invalid input.");
                isCorrect = false;
            }
            if (isCorrect && (pawnNum < 0 || pawnNum > 62)) {
                System.out.println("Error! You have to input number from 0 or 62.");
                isCorrect = false;
            }
        } while (!isCorrect);

        for (int i = 0; i < pawnNum; i++){

            System.out.println("Input position for the pawn number " + (i+1) + ": ");

            do {
                System.out.print("X: ");
                isCorrect = true;
                try {
                    x = scanner.nextInt();
                } catch (Exception e) {
                    System.out.println("Invalid input.");
                    isCorrect = false;
                    scanner.nextLine();
                }

                if (isCorrect && (x < 1 || x > 8)) {
                    System.out.println("Please enter a value from " + 1 + " to " + 8 + "!");
                    isCorrect = false;
                }
            } while (!isCorrect);

            do {
                System.out.print("Y : ");
                isCorrect = true;
                try {
                    y = scanner.nextInt();
                } catch (Exception e) {
                    System.out.println("Invalid input.");
                    isCorrect = false;
                    scanner.nextLine();
                }

                if (isCorrect && (y < 1 || y > 8)) {
                    System.out.println("Please enter a value from " + 1 + " to " + 8 + "!");
                    isCorrect = false;
                }
            } while (!isCorrect);

            ChessBoard[x-1][y-1] = -1;

        }
    return ChessBoard;
    }

    // Driver code
    public static void main(String[] args)
    {
        int N = 8;
        int[] knightPos = { 0, 0 };
        int[] targetPos = { 0, 0 };
        int[][] ChessBoard = new int[8][8];
        int minStep;

        Scanner scanner = new Scanner(System.in);

        System.out.println("This program finds shortest knight path from chess square (X1, Y1) to (X2, Y2).");

        int inputMethodChoice = chooseInputMethod();


        if (inputMethodChoice == 1) {
            knightPos = inputStartPosManually(scanner);
            targetPos = inputTargetPosManually(scanner);

            ChessBoard = AddPawns(scanner);
        } else if (inputMethodChoice == 2) {
            String filePath = findFile(scanner);
            ChessBoard = inputDataFromFile(filePath);

            for (int i = 0; i < 8; i++){
                for (int j = 0; j < 8; j++){
                    if (ChessBoard[i][j] == 0) {
                        knightPos[0] = i;
                        knightPos[1] = j;

                    } else if (ChessBoard[i][j] == 1){
                        targetPos[0] = i;
                        targetPos[1] = j;
                    }
                }
            }
        }

        // Function call
        minStep = minStepToReachTarget(knightPos, targetPos, N, ChessBoard);
        if (minStep > 1000){
            System.out.println("Target can not be reached!");
        } else {
            System.out.println("Minimal number of moves needed to reach target - " + minStep);
        }
    }

}