Untitled
plain_text
a month ago
3.4 kB
1
Indexable
Never
package d22; import java.util.Scanner; public class HugoDaoVang1 { public static int n,g,row,col; public static int arr[][] = new int[25][25]; public static int res[][][] = new int[25][25][5]; public static int G[][] = new int [5][2]; public static int que[][] = new int[10005][3]; public static int X[] = {0,0,1,-1}; public static int Y[] = {1,-1,0,0}; public static int check[][] = new int[25][25]; public static int check_g[] = new int [5]; public static int so_mo_vang_max,chi_phi_min,x_res,y_res; public static void BFS(int id_g){ int l=0,r=0; que[l][0] = G[id_g][0]; que[l][1] = G[id_g][1]; que[l][2] = 0; res[G[id_g][0]][G[id_g][1]][id_g] = 0; res[G[id_g][0]][G[id_g][1]][0] +=1; check[G[id_g][0]][G[id_g][1]]=1; int fr_x,fr_y,fr_step; while(l<=r){ fr_x = que[l][0]; fr_y = que[l][1]; fr_step = que[l][2]; for(int i=0;i<4;i++){ if(fr_x+X[i]>=1 && fr_x+X[i]<=n && fr_y+Y[i]>=1 && fr_y+Y[i]<=n && check[fr_x+X[i]][fr_y+Y[i]]==0 && arr[fr_x+X[i]][fr_y+Y[i]]!=0){ r++; que[r][0] = fr_x+X[i]; que[r][1] = fr_y+Y[i]; que[r][2] = fr_step+1; check[fr_x+X[i]][fr_y+Y[i]]=1; res[fr_x+X[i]][fr_y+Y[i]][id_g] = que[r][2]; res[fr_x+X[i]][fr_y+Y[i]][0]+=1; } } l++; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int test=1;test<=t;test++){ n = sc.nextInt(); g = sc.nextInt(); for(int i=1;i<=g;i++){ row = sc.nextInt(); col = sc.nextInt(); G[i][0] = row; G[i][1] = col; check_g[i] = 0; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ arr[i][j] = sc.nextInt(); // 0 la da, 1 la di duoc } } for(int i=1;i<=g;i++){ arr[G[i][0]][G[i][1]] = 2; // 2 la co vang } //solve for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=g;k++){ res[i][j][k] = 0; } } } for(int i=1;i<=g;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ check[j][k]=0; } } BFS(i); } // for(int k=1;k<=g;k++){ // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // System.out.print(res[i][j][k]+" "); // } // System.out.println(); // } // System.out.println("-------------------------------------------"); // } int ok = 0; so_mo_vang_max = 0; chi_phi_min = 0; x_res = 0; y_res = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(arr[i][j]==1){ int tmp_max = 0; for(int k=1;k<=g;k++){ if(res[i][j][k]!=0){ if(tmp_max<res[i][j][k]) tmp_max = res[i][j][k]; if(check_g[k]==0){ ok+=1; check_g[k]=1; } } } if(so_mo_vang_max<res[i][j][0]){ so_mo_vang_max = res[i][j][0]; chi_phi_min = tmp_max; x_res = i; y_res = j; }else if(so_mo_vang_max==res[i][j][0]){ if(chi_phi_min>tmp_max){ chi_phi_min = tmp_max; x_res = i; y_res = j; } } } } } System.out.println("Case #"+test); if(ok==0){ System.out.println("-1"); }else{ System.out.println(chi_phi_min); for(int i=1;i<=g;i++){ if(res[x_res][y_res][i]==0){ System.out.println(G[i][0]+" "+G[i][1]); } } } } } }