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