Untitled
unknown
plain_text
a year ago
4.1 kB
11
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);
}
}
}
Editor is loading...
Leave a Comment