Untitled
unknown
plain_text
a year ago
4.7 kB
2
Indexable
Never
import java.util.Scanner; public class Solution { static int n; static int m; static int[][] a; static int[][] vang; static int[] tansuat; static int[] tdx; static int[] tdy; static int k; static int[][] visit; static int[][] c; static int[][] b; static int[] d1 = {-1,1,0,0}; static int[] d2 = {0,0,-1,1}; public static void main(String[] args) { //System.setIn(new FileInputStream("src/Hugo_Dao_Vang_1/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int test_case = 1; test_case <= T; test_case++){ n = sc.nextInt(); m = sc.nextInt(); a = new int[n][n]; b = new int[n][n]; c = new int[n][n]; vang = new int[n][n]; visit = new int[n][n]; tansuat = new int[4]; tdx = new int[4]; tdy = new int[4]; k = 0; for(int i = 0; i < m; i++){ int l = sc.nextInt()-1; int r = sc.nextInt()-1; vang[l][r] = 1; tdx[k] = l; tdy[k] = r; k++; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ a[i][j] = sc.nextInt(); b[i][j] = -100; } } for(int i = 0; i < k; i++){ bfs(tdx[i], tdy[i]); /*for(int i1 = 0; i1 < n; i1++){ for(int j1 = 0; j1 < n; j1++){ System.out.print(visit[i1][j1] + " "); } System.out.println(); } System.out.println();*/ for(int j = 0; j < k; j++){ if(visit[tdx[j]][tdy[j]] == 1 && check(tdx[j], tdy[j])){ tansuat[i]++; } } update(); } /*for(int i = 0; i < k; i++){ System.out.println(tansuat[i]); }*/ int max = 0; for(int i = 0; i < k; i++){ if(max < tansuat[i]){ max = tansuat[i]; } } int u = -1; for(int i = 0; i < k; i++){ if(tansuat[i] == max){ u = i; break; } } update(); bfs(tdx[u], tdy[u]); for(int i = 0; i < k; i++){ if(visit[tdx[i]][tdy[i]] != 1){ tansuat[i] = 0; } } update(); for(int i = 0; i < k; i++){ if(tansuat[i] == max){ bfsTinh(tdx[i], tdy[i]); if(i==0){ gan(); } update(); } } int min = Integer.MAX_VALUE; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(min > c[i][j] && c[i][j] != 0 && vang[i][j] != 1){ min = c[i][j]; } } } /*for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ System.out.print(c[i][j] + " "); } System.out.println(); }*/ System.out.println("Case #" + test_case); if(min == Integer.MAX_VALUE){ System.out.println(-1); }else{ System.out.println(min); for(int i = 0; i < k; i++){ if(tansuat[i] == 0){ System.out.println((tdx[i]+1) + " " + (tdy[i]+1)); } } } } } public static void update(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ visit[i][j] = 0; b[i][j] = 0; } } } public static void gan(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ c[i][j] = b[i][j]; } } } public static void bfs(int u, int v){ int[] q = new int[405]; int[] w = new int[405]; int l = 0, r = 0; visit[u][v] = 1; q[r] = u; w[r] = v; r++; while(l < r){ int x = q[l]; int y = w[l]; l++; for(int i = 0; i < 4; i++){ int xx = x+d1[i]; int yy = y+d2[i]; if(xx>=0 && yy >=0 && xx<n && yy<n){ if(visit[xx][yy] == 0 && a[xx][yy] != 0){ visit[xx][yy] = 1; q[r] = xx; w[r] = yy; r++; } } } } } public static boolean kt(){ for(int i = 0; i < k; i++){ if(tansuat[i] != 0){ return false; } } return true; } public static boolean check(int u, int v){ visit[u][v] = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(visit[i][j] != 0){ return true; } } } return false; } public static void bfsTinh(int u, int v){ int[] q = new int[405]; int[] w = new int[405]; int l = 0, r = 0; b[u][v] = 0; visit[u][v] = 1; q[r] = u; w[r] = v; r++; while(l < r){ int x = q[l]; int y = w[l]; l++; for(int i = 0; i < 4; i++){ int xx = x+d1[i]; int yy = y+d2[i]; if(xx>=0 && yy >=0 && xx<n && yy<n){ if(a[xx][yy] != 0 && visit[xx][yy] == 0){ visit[xx][yy] = 1; b[xx][yy] = b[x][y] + 1; if(c[xx][yy] < b[xx][yy]){ c[xx][yy] = b[xx][yy]; } q[r] = xx; w[r] = yy; r++; } } } } } }