Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
3.3 kB
0
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;

public class GridAcid {
	static{
		try {
			System.setIn(new FileInputStream("src/inp.txt"));
//			System.setOut(new PrintStream("src/out.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	static Scanner scanner=new Scanner(System.in);
	static StringBuilder builder=new StringBuilder();
	
	static class Node{
		int x,y;
		Node link;
		Node(int x,int y){
			this.x=x;this.y=y;
		}
	}
	
	static class Queue{
		Node front,rear;
		int n;
		void push(Node node){
			++n;
			if(front==null){
				front=rear=node;
				return;
			}
			rear.link=node;
			rear=node;
		}
		void pop(){
			if(front==null)
				return;
			--n;
			front=front.link;
			if(front==null)
				rear=null;
		}
	}
	
	static int[][] dir={{-1,0},{0,-1},{0,1},{1,0}};
	
	static void exec(int test){
		int n=Integer.parseInt(scanner.next()),
			m=Integer.parseInt(scanner.next());
		/*n: so hang, m: so cot
		 * sau do la vi tri do acid
		 * 0: stone,
		 * 1: metal
		 * 2: emptu
		 * nxm ma tran,
		 * do len o metal => co the lam nong chay no
		 * stone ko the di qua no
		 * empty: co the di qua
		 * 
		 * output khi nao o trong bi acid chiem va toan bo matrix bi day,
		 * 1s de tran den o rong
		 * */
		int ax=Integer.parseInt(scanner.next()),ay=Integer.parseInt(scanner.next());
		--ay;--ax;
		int ex=0,ey=0;
		int[][] arr=new int[n][m];
		
		for(int i=0;i<n;++i) for(int j=0;j<m;++j){
			arr[i][j]=Integer.parseInt(scanner.next());
			if(arr[i][j]==2){
				ex=i;
				ey=j;
			}
		}
		
		for(int i=0;i<4;++i){
			int nxe=ex+dir[i][0],nye=ey+dir[i][1];
			if(nxe<0 || nxe>=n || nye<0 || nye>=m || arr[nxe][nye]==0){
				System.out.printf("Case #%d\n%d %d\n",test,-1,-1);
				return;
			}
		}
		
		Queue queue=new Queue();
		boolean[][] M=new boolean[n][m];
		int cost[][]=new int[n][m];
		int tot=1;
		for(int i=0;i<n;++i) for(int j=0;j<m;++j) cost[i][j]=Integer.MAX_VALUE;
		M[ax][ay]=true;
		queue.push(new Node(ax,ay));
		cost[ax][ay]=1;
		
		while(queue.n>0){
			int x=queue.front.x,
				y=queue.front.y;
			queue.pop();
			
			tot=Math.max(tot,cost[x][y]);
			
			for(int i=0;i<4;++i){
				int nx=x+dir[i][0],ny=y+dir[i][1];
				if(nx>=0 && nx<n && ny>=0 && ny<m && !M[nx][ny] && arr[nx][ny]==1){
					M[nx][ny]=true;
					cost[nx][ny]=cost[x][y]+1;
					queue.push(new Node(nx,ny));
				}
			}
		}
		
		int maxemp=0;
		for(int i=0;i<4;++i){
			int nxe=ex+dir[i][0],nye=ey+dir[i][1];
			if(nxe>=0 && nxe<n && nye>=0 && nye<m && cost[nxe][nye]!=Integer.MAX_VALUE)
				maxemp=Math.max(maxemp,cost[nxe][nye]);
			else{
				System.out.printf("Case #%d\n%d %d\n",test,-1,-1);
				return;
			}
		}
		
		for(int i=0;i<n;++i)
			for(int j=0;j<m;++j)
				if(arr[i][j]==1 && cost[i][j]==Integer.MAX_VALUE){
					System.out.printf("Case #%d\n%d %d\n",test,maxemp,-1);
					return;
				}
		
		System.out.printf("Case #%d\n%d %d\n",test,maxemp,tot);
	}
	
	public static void main(String[] args) {
		int t=Integer.parseInt(scanner.next());
		
		for(int test=1;test<=t;++test)
			exec(test);
		
		scanner.close();
	}
}