find shortest path

import java.util.Scanner;

public class ShortestPathInMatrix {
    // Lớp để lưu trữ tọa độ
    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

// Lớp Queue tự triển khai
    static class Queue {
        private static class Node {
            Point point;
            Node next;
            Node(Point point) {
                this.point = point;
                this.next = null;
            }
        }
        
        Node front, rear;
        int size;

Queue() {
            front = rear = null;
            size = 0;
        }

void enqueue(Point point) {
            Node newNode = new Node(point);
            if (rear == null) {
                front = rear = newNode;
            } else {
                rear.next = newNode;
                rear = newNode;
            }
            size++;
        }

Point dequeue() {
            if (isEmpty()) return null;
            Point point = front.point;
            front = front.next;
            if (front == null) rear = null;
            size--;
            return point;
        }

boolean isEmpty() {
            return size == 0;
        }
    }

// Hàm tìm đường đi ngắn nhất
    public static int findShortestPath(int[][] matrix, Point start, Point end) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return -1;
        int rows = matrix.length;
        int cols = matrix[0].length;

// Kiểm tra điểm bắt đầu và kết thúc hợp lệ
        if (start.x < 0 || start.x >= rows || start.y < 0 || start.y >= cols ||
            end.x < 0 || end.x >= rows || end.y < 0 || end.y >= cols ||
            matrix[start.x][start.y] == 1 || matrix[end.x][end.y] == 1) {
            return -1;
        }

// Mảng đánh dấu các ô đã thăm
        boolean[][] visited = new boolean[rows][cols];
        // Mảng lưu khoảng cách từ điểm bắt đầu
        int[][] distance = new int[rows][cols];
        
        // Các hướng di chuyển: lên, phải, xuống, trái
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

Queue queue = new Queue();
        queue.enqueue(start);
        visited[start.x][start.y] = true;
        distance[start.x][start.y] = 0;

while (!queue.isEmpty()) {
            Point current = queue.dequeue();
            
            // Nếu đến được điểm kết thúc
            if (current.x == end.x && current.y == end.y) {
                return distance[current.x][current.y];
            }

// Kiểm tra 4 hướng
            for (int i = 0; i < 4; i++) {
                int newX = current.x + dx[i];
                int newY = current.y + dy[i];

// Kiểm tra điều kiện hợp lệ
                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols 
                    && !visited[newX][newY] && matrix[newX][newY] == 0) {
                    queue.enqueue(new Point(newX, newY));
                    visited[newX][newY] = true;
                    distance[newX][newY] = distance[current.x][current.y] + 1;
                }
            }
        }

// Không tìm thấy đường đi
        return -1;
    }

// Hàm main để nhập ma trận và hai điểm bất kỳ
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

// Nhập kích thước ma trận
        System.out.print("Nhập số hàng của ma trận: ");
        int rows = scanner.nextInt();
        System.out.print("Nhập số cột của ma trận: ");
        int cols = scanner.nextInt();

// Nhập ma trận
        int[][] matrix = new int[rows][cols];
        System.out.println("Nhập ma trận (0: đi được, 1: bị chặn):");
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

// Nhập điểm bắt đầu
        System.out.print("Nhập tọa độ điểm bắt đầu (x y): ");
        int startX = scanner.nextInt();
        int startY = scanner.nextInt();
        Point start = new Point(startX, startY);

// Nhập điểm kết thúc
        System.out.print("Nhập tọa độ điểm kết thúc (x y): ");
        int endX = scanner.nextInt();
        int endY = scanner.nextInt();
        Point end = new Point(endX, endY);

// Tìm đường đi ngắn nhất
        int result = findShortestPath(matrix, start, end);
        if (result != -1) {
            System.out.println("Độ dài đường đi ngắn nhất: " + result);
        } else {
            System.out.println("Không tồn tại đường đi");
        }

scanner.close();
    }
}