Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
4.1 kB
2
Indexable
//
//import java.util.LinkedList;
//import java.util.Queue;
//import java.util.Scanner;
//
//public class Main {
//    static int M, N;
//    static int[] x = {0, -1, 0, 1};
//    static int[] y = {-1, 0, 1, 0};
//    static int[][] visited;
//    static Queue<Integer> q = new LinkedList<Integer>();
//    static Scanner sc = new Scanner(System.in);
//    static int[][] matrix = new int[M][N];
//    public static void input_matrix() {
//        for (int i = 0; i < M; i++) {
//            for (int j = 0; j < N; j++) {
//                matrix[i][j] = sc.nextInt();
//                visited[i][j] = 0;
//            }
//        }
//    }
//
//    public static void BFS(int idx, int idy) {
//        q.add(idx);
//        q.add(idy);
//        while (!q.isEmpty()) {
//            int r = q.poll();
//            int c = q.poll();
//            visited[r][c] = 1;
//            for (int i = 0; i < 4; i++) {
//                int new_r = r + x[i];
//                int new_c = c + y[i];
//                if (new_r < 0 || new_r >= M - 1 || new_c < 0 || new_c >= N - 1 || visited[new_r][new_c] != 0) {
//                    break;
//                } else {
//                    visited[new_r][new_c] = visited[r][c] + 1;
//                    q.add(new_r);
//                    q.add(new_c);
//                }
//            }
//        }
//    }
//
//    public static void main(String[] args) {
//        M = sc.nextInt();
//        N = sc.nextInt();
//        int idx = sc.nextInt();
//        int idy = sc.nextInt();
//        input_matrix();
//        BFS(idx - 1, idy - 1);
//        int temp = -1;
//        for (int i = 0; i < M; i++) {
//            for (int j = 0; j < N; j++) {
//                if (i == 0 ||j == 0 || i == M - 1 || j == N - 1 && visited[i][j] > temp) {
//                    temp = visited[i][j];
//                }
//            }
//        }
//        System.out.println(temp);
//    }
//}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int M, N;
    static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
    static int[][] visited;
    static Queue<int[]> q = new LinkedList<>();
    static Scanner sc = new Scanner(System.in);
    static int[][] matrix;

    public static void input_matrix() {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
                visited[i][j] = 0;
            }
        }
    }

    public static void BFS(int idx, int idy) {
        q.add(new int[] {idx, idy});
        visited[idx][idy] = 1;
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0];
            int c = current[1];

            for (int i = 0; i < 4; i++) {
                int new_r = r + x[i];
                int new_c = c + y[i];

                if (new_r >= 0 && new_r < M && new_c >= 0 && new_c < N && visited[new_r][new_c] == 0 && matrix[new_r][new_c] == 0) {
                    visited[new_r][new_c] = visited[r][c] + 1;
                    q.add(new int[] {new_r, new_c});
                }
            }
        }
    }

    public static void main(String[] args) {
        M = sc.nextInt();
        N = sc.nextInt();
        int idx = sc.nextInt();
        int idy = sc.nextInt();

        matrix = new int[M][N];
        visited = new int[M][N];
        input_matrix();
        BFS(idx - 1, idy - 1);

        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 0 && (i == 0 || j == 0 || i == M - 1 || j == N - 1) && visited[i][j] != 0) {
                    minDist = Math.min(minDist, visited[i][j]);
                }
            }
        }
        if (minDist == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(minDist);
        }
    }
}
Leave a Comment