Untitled
unknown
plain_text
a year ago
3.5 kB
4
Indexable
Case #1: 1 / Case #2: 2 / Case #3: 2 / Case #4: 7 / Case #5: 3 / 1 9 / Case #6: 8 / Case #7: 2 / Case #8: 4 / Case #9: 6 / Case #10: 1 / 8 4 / Case #11: 1 / 4 3 / 4 5 / 6 10 / Case #12: 1 / Case #13: 4 / 6 8 / Case #14: 6 / 3 9 / Case #15: 1 / 1 7 / 9 10 / 7 2 / Case #16: 1 / 3 6 / Case #17: 8 / Case #18: 1 / 10 10 / Case #19: 3 / 6 8 / Case #20: 7 / Case #21: 7 / Case #22: 2 / Case #23: 10 / Case #24: 9 / Case #25: 2 / 11 10 / 10 10 / Case #26: 6 / Case #27: 1 / 2 11 / Case #28: 1 / 9 8 / Case #29: 8 / Case #30: 3 / Case #31: 5 / Case #32: 10 / Case #33: 12 / Case #34: 12 / Case #35: 5 / 2 2 / Case #36: 13 / Case #37: 12 / 6 10 / 4 15 / Case #38: 8 / Case #39: 3 / Case #40: 11 / Case #41: 1 / 5 14 / Case #42: 8 / Case #43: 1 / 18 14 / Case #44: 10 / Case #45: 10 / 20 13 / Case #46: 8 / 18 2 / Case #47: 7 / Case #48: -1 / Case #49: 11 / Case #50: 1 / 17 2 public class Solution { static final int MS = 30; static int n, g, maxx, minn, cg; static int[] gx = new int[MS]; static int[] gy = new int[MS]; static int[][] m = new int[MS][MS]; static int[][] ig = new int[MS][MS]; static int[][] check = new int[MS][MS]; static boolean[] c = new boolean[MS]; static boolean[] c_tmp = new boolean[MS]; static int[] dx = { -1, 0, 1, 0 }; static int[] dy = { 0, 1, 0, -1 }; static Queue<Point> q; static void BFS(int xh, int yh) { maxx = 0; cg = 0; c_tmp = new boolean[g]; check = new int[MS][MS]; q.reset(); q.enQueue(new Point(xh, yh)); check[xh][yh] = 1; Point p; while (!q.isEmpty()) { p = q.peek(); q.deQueue(); for (int i = 0; i < 4; i++) { int xx = p.x + dx[i]; int yy = p.y + dy[i]; if (isSafe(xx, yy) && check[xx][yy] == 0) { check[xx][yy] = check[p.x][p.y] + 1; q.enQueue(new Point(xx, yy)); if (m[xx][yy] == 9) { cg++; c_tmp[ig[xx][yy]] = true; maxx = Math.max(maxx, check[xx][yy] - 1); } } } } } private static boolean isSafe(int xx, int yy) { if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && m[xx][yy] != 0) { return true; } return false; } public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); q = new Queue<>(); for (int tc = 1; tc <= T; tc++) { n = sc.nextInt(); g = sc.nextInt(); for (int i = 0; i < g; i++) { gx[i] = sc.nextInt(); gy[i] = sc.nextInt(); ig[gx[i]][gy[i]] = i; c[i] = false; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { m[i][j] = sc.nextInt(); } } for (int i = 0; i < g; i++) { m[gx[i]][gy[i]] = 9; } maxx = 0; minn = 999999; int sl = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (m[i][j] == 1) { BFS(i, j); if (cg > sl) { sl = cg; minn = maxx; for (int k = 0; k < g; k++) { c[k] = c_tmp[k]; } } else if (cg == sl) { if (maxx != 0) { if (minn > maxx) { minn = maxx; for (int k = 0; k < g; k++) { c[k] = c_tmp[k]; } } } } } } } System.out.println("Case #" + tc); if (minn == 999999) { System.out.println(-1); } else { System.out.println(minn); for (int i = 0; i < g; i++) { if (!c[i]) { System.out.println(gx[i] + " " + gy[i]); } } } } } }
Editor is loading...
Leave a Comment