# Untitled

unknown
plain_text
a month ago
3.1 kB
1
Indexable
Never
```package Grid_Acid;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static int n, m, res1, res2, count1, count2;
static int[][] a = new int[3005][3005], lan = new int[3005][3005], visit = new int[3005][3005];
static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };

public static boolean da_1(int x, int y) {
for (int i = 0; i < 4; i++) {
int newx = x + dx[i], newy = y + dy[i];
if (newx < 0 || newy < 0 || newx >= n || newy >= m
|| a[newx][newy] == 0) {
return true;
}
}
return false;
}

public static int da_4(int x, int y) {
int count = 0;
for (int i = 0; i < 4; i++) {
int newx = x + dx[i], newy = y + dy[i];
if (newx >= 0 && newy >= 0 && newx < n && newy < m
&& visit[newx][newy] == 1) {
count++;
}
}
return count;
}

public static void BFS(int xstart, int ystart) {
int front = 0, rear = 0;
int[] queueX = new int[9000005], queueY = new int[9000005];
queueX[front] = xstart;
queueY[front] = ystart;
lan[xstart][ystart] = 0;
visit[xstart][ystart] = 1;
while (front <= rear) {
int x = queueX[front], y = queueY[front];
int c = lan[x][y];
res2 = c;
count1--;
for (int i = 0; i < 4; i++) {
int newx = x + dx[i], newy = y + dy[i];
if (newx >= 0 && newy >= 0 && newx < n && newy < m
&& visit[newx][newy] == 0 && a[newx][newy] != 0) {
if(a[newx][newy] == 1){
rear++;
queueX[rear] = newx;
queueY[rear] = newy;
visit[newx][newy] = 1;
lan[newx][newy] = c+1;
}else if(a[newx][newy] == 2 && da_4(newx, newy) == 4){
visit[newx][newy] = 1;
lan[newx][newy] = c+1;
}
}
}
front++;
}
}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
int test = scanner.nextInt();
for (int t = 1; t <= test; t++) {
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = 0;
lan[i][j] = 0;
visit[i][j] = 0;
}
}
int x = scanner.nextInt()-1, y = scanner.nextInt()-1;
count1 = 0; count2 = 0;
int xda = 0, yda = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = scanner.nextInt();
if(a[i][j] == 2){
xda = i;
yda = j;
}
if(a[i][j] == 1){
count1 ++;
}
}
}

res1 = 0; res2 = 0;
if(da_1(xda, yda)){
res1 = -1; res2 = -1;
}else{
BFS(x, y);
if(da_4(xda, yda) != 4){
res1 = -1; res2 = -1;
}else{
res1 = lan[xda][yda];
if(count1>0){
res2 = -1;
}else{
res2++ ;
}
}

}

System.out.println("Case #" + t +"\n" + res1 + " " + res2);
}
scanner.close();
}
}
```