Untitled
plain_text
23 days ago
2.6 kB
3
Indexable
Never
package LABYR1_Me_Cung; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int n,m; static int[][] a; static int[] d1 = {0,0,-1,1}; static int[] d2 = {-1,1,0,0}; static int[][] visit; static int[][] b; public static void main(String args[]) throws Exception{ System.setIn(new FileInputStream("src/LABYR1_Me_Cung/input.txt")); Scanner sc = new Scanner(System.in); int T; int Answer; T=Integer.parseInt(sc.nextLine()); for(int test_case = 1; test_case <= T; test_case++){ String s = sc.nextLine(); String[] temp = s.trim().split(" "); m = Integer.parseInt(temp[0]); n = Integer.parseInt(temp[1]); a = new int[n][m]; visit = new int[n][m]; b = new int[n][m]; for(int i = 0; i < n; i++){ String str = sc.nextLine(); for(int j = 0; j < str.length(); j++){ if(str.charAt(j) == '#'){ a[i][j] = 0; }else if(str.charAt(j) == '.'){ a[i][j] = 1; } } } int x = -1; int y = -1; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(a[i][j] == 1){ bfs(i,j); int max = 0; for(int u = 0; u < n; u++){ for(int z = 0; z < m; z++){ if(b[u][z] != 0 && max < b[u][z]){ max = b[u][z]; x = u; y = z; } } } update(); i = n; j = m; } } } if(x == -1 && y == -1){ System.out.println("Maximum rope length is 0."); }else{ bfs(x,y); int kq = xl(); System.out.println("Maximum rope length is " + kq + "."); } } } public static void bfs(int u, int v){ int[] q = new int[1000*1000+5]; int[] w = new int[1000*1000+5]; visit[u][v] = 1; b[u][v] = 0; int l = 0, r = 0; 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<m){ if(visit[xx][yy] == 0 && a[xx][yy] == 1){ visit[xx][yy] = 1; b[xx][yy] = b[x][y] + 1; q[r] = xx; w[r] = yy; r++; } } } } } public static int xl(){ int max = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(max < b[i][j]){ max = b[i][j]; } } } return max; } public static void update(){ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ visit[i][j] = 0; b[i][j] = 0; } } } }