Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.9 kB
4
Indexable
Never
package Grid_Axit;

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

public class grid_acid {
	static int MAX_SIZE = 100000;
	static int [][] queue = new int [MAX_SIZE][2];
	static int rear, front;
	static void push(int x, int y) {
		if(rear == MAX_SIZE - 1) rear = -1;
		rear++;
		queue[rear][0] = x;
		queue[rear][1] = y;
	}
	
	static void pop() {
		if(front == MAX_SIZE -1) front = -1;
		front++;
	}
	
	static boolean isEmpty() {
		return rear == front;
	}
	
	
	static int m, n, ex, ey, ax, ay;
	static int count1, count2;
	static int [][] map;
	static int [] dx = {0, 1, 0, -1};
	static int [] dy = {1, 0, -1, 0};
	
	static void bfs(int x, int y) {
		push(x, y);
		while (!isEmpty()) {
			pop();
			int a = queue[front][0];
			int b = queue[front][1];
			for(int i = 0; i < 4; i++) {
				int x1 = a + dx[i];
				int y1 = b + dy[i];
				if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < m && map[x1][y1] == 1) {
					map[x1][y1] = map[a][b] + 1;
					push(x1, y1);
				}
			}
			System.out.println();
		}
	}
	
	static void checkCell() {
		for(int i = 0; i < 4; i++) {
			int x1 = ex + dx[i];
			int y1 = ey + dy[i];
			if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < m) {
				if (map[x1][y1] > 1 || (map[x1][y1] == 1 && x1 == ax && y1 == ay)) {
					if (map[x1][y1] > count1) {
						count1 = map[x1][y1];
					}
				} else {
					count1 = count2 = -1;
					return;
				}
				
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++){
				if (map[i][j] == 1) {
					count2 = -1;
					return;
				} else if (map[i][j] > count2){
					count2 = map[i][j];
				}
			}
		}
	}
	
	
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("D://Trainee//SRV_training//src//Grid_Axit//acid.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			rear = front = -1;
			n = sc.nextInt();
			m = sc.nextInt();
			ax = sc.nextInt() - 1;
			ay = sc.nextInt() - 1;
			map = new int [n][m];
			boolean flag = true;
			count1 = count2 = -1;
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++){
					map[i][j] = sc.nextInt();
					if(map[i][j] == 2) {
						if(i == 0 || i == n - 1 || j == 0 || j == m - 1) {
							System.out.println("Case #" + test_case);
							System.out.println(count1 + " " + count2);
							flag = false;
						}
						ex = i;
						ey = j;
					}
				}
			}
			if (!flag) continue;
			boolean check = true;
			
			// neu acid do vao da thi return -1
			if (map[ax][ay] != 0) {
				bfs(ax, ay);
			} 
			else {
				check = false;
			}
			
			if (check) {
				checkCell();
			}
			
			System.out.println("Case #" + test_case);
			System.out.println(count1 + " " + count2);
		}

	}

}