Untitled

mail@pastecode.io avatar
unknown
plain_text
25 days ago
2.7 kB
2
Indexable
Never
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class FastRobot {
    static final int MAX = 201;
    static final char WALL = '1';
    static int T;
    static int n, m;
    static char[][] a = new char[MAX][MAX];
    static int startX, startY, endX, endY;
    static int[] moveY = {0, 0, -1, 1}; // lên, xuống
    static int[] moveX = {-1, 1, 0, 0}; // trái, phải
    static int[][] cost = new int[MAX][MAX]; // chi phí để đi đến từng ô

    // Class Point để lưu tọa độ điểm
    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // Đọc dữ liệu đầu vào
    static void input(Scanner scanner) {
        m = scanner.nextInt(); // số cột
        n = scanner.nextInt(); // số hàng
        startY = scanner.nextInt();
        startX = scanner.nextInt();
        endY = scanner.nextInt();
        endX = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            String row = scanner.next();
            for (int j = 1; j <= m; j++) {
                a[i][j] = row.charAt(j - 1);
                cost[i][j] = -1;
            }
        }
    }

    // Kiểm tra ô hợp lệ
    static boolean checkValidCell(int x, int y) {
        return !(x < 1 || x > n || y < 1 || y > m || a[x][y] == WALL);
    }

    // Tìm đường đi nhanh nhất cho robot
    static void fastRobot() {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(startX, startY));
        cost[startX][startY] = 0;
        while (!queue.isEmpty()) {
            Point currPos = queue.poll();
            for (int i = 0; i < 4; i++) {
                int currX = currPos.x;
                int currY = currPos.y;
                while (true) {
                    int nextX = currX + moveX[i];
                    int nextY = currY + moveY[i];
                    if (!checkValidCell(nextX, nextY)) break;
                    if (cost[nextX][nextY] == -1) {
                        cost[nextX][nextY] = cost[currPos.x][currPos.y] + 1;
                        queue.add(new Point(nextX, nextY));
                    }
                    currX = nextX;
                    currY = nextY;
                }
            }
        }
    }

    // Hàm main
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            input(scanner);
            fastRobot();
            int result = cost[endX][endY] - 1;
            System.out.println(result != -1 ? result : -1);
        }
        scanner.close();
    }
}
Leave a Comment