Untitled
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(); } }