Untitled
unknown
plain_text
2 years ago
3.3 kB
9
Indexable
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();
}
}
Editor is loading...