Untitled

mail@pastecode.io avatarunknown
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;
			}
		}
	}
}