Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
0
Indexable
Never
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;
		
	}
}