Untitled
plain_text
a month ago
2.8 kB
1
Indexable
Never
package hugo_dao_vang_1; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, res, g, check, mo; static int[][] a, visit, golden, value; static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 }; static int[] gx = new int[5], gy = new int[5]; static int[] nox = new int[5], noy = new int[5]; static int[] qx = new int[1000], qy = new int[1000]; static boolean checkOut(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= n) return false; return true; } static void BFS(int x, int y) { visit = new int[n][n]; value = new int[n][n]; int front = 0, rear = 1; qx[front] = x; qy[front] = y; visit[x][y] = 1; while (front < rear) { int xt = qx[front], yt = qy[front], c = value[xt][yt]; for (int i = 0; i < 4; i++) { int nx = xt + dx[i], ny = yt + dy[i]; if (checkOut(nx, ny) && a[nx][ny] == 1 && visit[nx][ny] == 0) { qx[rear] = nx; qy[rear] = ny; rear++; visit[nx][ny] = 1; value[nx][ny] = c + 1; } } front++; } int max = 0; int dem = 0; for (int i = 0; i < g; i++) { if (value[gx[i]][gy[i]] > max) { max = value[gx[i]][gy[i]]; } if (visit[gx[i]][gy[i]] == 1) { dem++; } } if((dem > mo) || ((dem == mo && dem != 0) && max < res)){ res = max; mo = dem; int count = 0; for (int i = 0; i < g; i++) { if (visit[gx[i]][gy[i]] == 0) { nox[count] = gx[i]; noy[count] = gy[i]; count++; } } } } 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(); g = scanner.nextInt(); a = new int[n][n]; golden = new int[n][n]; for (int i = 0; i < g; i++) { gx[i] = scanner.nextInt() - 1; gy[i] = scanner.nextInt() - 1; golden[gx[i]][gy[i]] = 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = scanner.nextInt(); } } res = Integer.MAX_VALUE; mo = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 1 && golden[i][j] == 0) { BFS(i, j); } } } if (mo == 0) { System.out.println("Case #" + t + "\n" + -1); } else { System.out.println("Case #" + t + "\n" + res); for (int i = 0; i < g - mo; i++) { System.out.println((nox[i] + 1) + " " + (noy[i] + 1)); } } // System.out.println("-----------"); } scanner.close(); } }