Untitled
unknown
plain_text
2 years ago
2.7 kB
4
Indexable
import java.util.Scanner;
public class Solution {
public static int[] dx = {-1,0,1,0};
public static int[] dy = {0,1,0,-1};
public static class Queue{
public int arr[];
public int front,rear;
public int size;
public Queue (int capacity){
rear = -1;
front = -1;
size = 0;
arr = new int[capacity];
}
public boolean isEmpty(){
return size == 0;
}
public boolean isFull(){
return size == arr.length;
}
public boolean enqueue(int item){
if(!isFull()){
rear++;
arr[rear] = item;
size++;
return true;
}
return false;
}
public int dequeue(){
int value = -1;
if(!isEmpty()){
front++;
value = arr[front];
size--;
return value;
}
return value;
}
public void Show(){
for(int i =front+1;i<=rear;i++){
System.out.println(arr[i]+" ");
}
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int Testcase = sc.nextInt();
for (int t = 1; t <= Testcase; t++) {
int N = sc.nextInt();
int M = sc.nextInt();
int[][] arr = new int[N][M];
int rowStart = sc.nextInt()-1;
int colStart = sc.nextInt()-1;
int rowEnd = 0;
int colEnd = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
arr[i][j] = sc.nextInt();
if(arr[i][j] == 2 ){
rowEnd = i;
colEnd = j;
}
}
}
Queue q1 = new Queue(50000000);
Queue q2 = new Queue(50000000);
boolean[][] visit = new boolean[N][M];
int result = bfs(rowStart,colStart,rowEnd, colEnd, arr,visit,arr, q1, q2, N, M);
System.out.println("Case #" + t);
if(result == -1){
System.out.println("-1 -1" );
}
else{
System.out.println(result + " " + result);
}
}
}
private static int bfs(int rowStart, int colStart, int rowEnd,int colEnd,int[][] arr,
boolean[][] visit, int[][] step, Queue q1,Queue q2, int N,int M) {
q1.enqueue(rowStart);
q2.enqueue(colStart);
visit[rowStart][colStart] = true;
while (!q1.isEmpty() && !q2.isEmpty()) {
int curR = q1.dequeue();
int curC = q2.dequeue();
if(visit[rowEnd-1][colEnd] && visit[rowEnd][colEnd+1] && visit[rowEnd+1][colEnd] && visit[rowEnd][colEnd-1]){
return step[curR][curC];
}
for(int i =0;i<4;i++){
int nextR = curR + dx[i];
int nextC = curC + dy[i];
if(nextC>=0 && nextC<M && nextR>=0 && nextR<N && !visit[nextR][nextC] && arr[nextR][nextC]==1){
visit[nextR][nextC] = true;
step[nextR][nextC] = step[curR][curC] + 1;
q1.enqueue(nextR);
q2.enqueue(nextC);
}
}
}
return -1;
}
}
Editor is loading...