Untitled
// //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