Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.2 kB
0
Indexable
Never
package day19_2306;

import java.util.Scanner;

class MyQueue{
	private int front, rear, max, cnt;
	private int[] q;
	
	public MyQueue(int a) {
		// TODO Auto-generated constructor stub
		front = 0;
		rear = -1;
		max = a;
		cnt = 0;
		q = new int[a];
	}
	
	public boolean isEmpty() {
		return cnt == 0;
	}
	
	public void enqueue(int a) {
		rear = (rear + 1) % max;
		q[rear] = a;
		cnt++;
	}
	
	public int dequeue() {
		int a = q[front];
		front = (front + 1) % max;
		cnt--;
		return a;
	}
}

public class grid_cell {
	
	static int row, col, xpour, ypour;
	static int xSpecial, ySpecial, numMetal, time;
	static int[][] map, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
	static int[][] visit;
	static boolean fillS;
	static MyQueue qx, qy;
	
	private static void BFS(){
		qx = new MyQueue(row * col);
		qy = new MyQueue(row * col);
		qx.enqueue(xpour); qy.enqueue(ypour);
		fillS = false;
		
		int x, y, dx, dy;
		while(!qx.isEmpty()){
			x = qx.dequeue(); y = qy.dequeue();
			for(int i = 0; i < 4; i++){
				dx = x + d[0][i]; dy = y + d[1][i];
				if(dx < row && dy < col && dx >= 0 && dy >= 0 && visit[dx][dy]== 0 && map[dx][dy] == 1){
					time = visit[dx][dy] = visit[x][y] + 1;
					qx.enqueue(dx); qy.enqueue(dy);
					if(checkSpecial() && !fillS){
						visit[xSpecial][ySpecial] = visit[x][y] + 1;
						fillS = true;
					}
					
				}
			}
		}
		
	}
	
	private static boolean checkMeltSpecial(){
		int dx, dy;
		for(int i = 0; i < 4; i++){
			dx = xSpecial + d[0][i]; dy = ySpecial + d[1][i];
			if(dx < 0 || dy < 0 || dx >= row || dy >= col || visit[dx][dy] == -1) return false;
		}
		return true;
	}
	
	private static boolean checkSpecial(){
		int dx, dy;
		for(int i = 0; i < 4; i++){
			dx = xSpecial + d[0][i]; dy = ySpecial + d[1][i];
			if(visit[dx][dy] == 0) return false;
		}
		return true;
	}
	
	private static boolean checkFullMelted(){
		if(!fillS) return false;
		else
		{
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					if(visit[i][j] == 0) return false;
				}
			}
		}
		
		return true;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			row = sc.nextInt();  col = sc.nextInt();
			xpour = sc.nextInt() - 1; ypour = sc.nextInt() - 1;
			
			map = new int[row][col];
			visit = new int[row][col];
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					map[i][j] = sc.nextInt();
					if(map[i][j] == 0) visit[i][j] = -1;
					else if(map[i][j] == 2){
						xSpecial = i; ySpecial = j;
					}
				}
			}
			

			System.out.println("Case #" + tc);
			if(map[xpour][ypour] == 0 || !checkMeltSpecial()){
				System.out.println(-1 + " " + -1);
			}
			else
			{
				visit[xpour][ypour] = 1;
				BFS();
				if(fillS) System.out.print(visit[xSpecial][ySpecial] + " ");
				else System.out.print(-1 + " ");
				if(!checkFullMelted()) System.out.println(-1);
				else System.out.println(time);
				
			}
		}
	}
}