[BOJ] 27311. 치노의 라떼 아트 (Easy)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int t = 0; t < T; t++) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			
			char[][] latte = new char[N][M];
			
			for(int i = 0; i < N; i++) {
				String s = sc.next();
				for(int j = 0; j < M; j++) {
					latte[i][j] = s.charAt(j);			
				}
			}
			
			Point leftUpSharpPoint = null;
			Point rightDownSharpPoint = null;
			Point rightUpSharpPoint = null; 
			Point leftDownSharpPoint = null;
			
			boolean isBreakAll = false; 
			for(int i = 0; i < N; i++) {
				if(isBreakAll) break;
				for(int j = 0; j < M; j++) {
					 if(latte[i][j] == '#') {
						 leftUpSharpPoint = new Point(i,j);
						 isBreakAll = true;
						 break;
					 }					 
				}				
			}
			
			isBreakAll = false;
			for(int i = N - 1; i >= 0; i--) {
				if(isBreakAll) break;
				for(int j = M - 1; j >= 0; j--) {
					if(latte[i][j] == '#') {
						rightDownSharpPoint = new Point(i,j);
						isBreakAll = true;
						break;						
					}
				}
			}
			
			isBreakAll = false;
			for(int i = 0; i < N; i++) {
				if(isBreakAll) break;
				for(int j = M - 1; j >= 0; j--) {
					if(latte[i][j] == '#') {
						rightUpSharpPoint = new Point(i,j);
						isBreakAll = true;
						break;
					}
				}			
			}
			
			isBreakAll = false;
			for(int i = N - 1; i >= 0; i--) {
				if(isBreakAll) break;
				for(int j = 0; j < M; j++) {
					if(latte[i][j] == '#') {						
						leftDownSharpPoint = new Point(i,j);
						isBreakAll = true;
						break;
					}
				}
			}
	
			int sharpCount = count(leftUpSharpPoint, rightDownSharpPoint, latte, '#');
			int dotCount = count(leftUpSharpPoint, rightDownSharpPoint, latte, '.');
			
			if(isSquareNumber(sharpCount + dotCount) && isSquareNumber(dotCount) && isDotsSquaredAndInCorner(leftUpSharpPoint, rightDownSharpPoint, latte, dotCount)) {			
				System.out.println(1);	
				continue;
			}
					
			sharpCount = count(leftDownSharpPoint, rightUpSharpPoint, latte, '#');
			dotCount = count(leftDownSharpPoint, rightUpSharpPoint, latte, '.');

			if(isSquareNumber(sharpCount + dotCount) && isSquareNumber(dotCount) && isDotsSquaredAndInCorner(leftDownSharpPoint, rightUpSharpPoint, latte, dotCount)) {
				System.out.println(1);	
				continue;
			}			
			System.out.println(0);
		}
	}	
	
	public static int count(Point p1, Point p2, char[][] arr, char ch) {
		if(p1 == null || p2 == null) return 0;
		int result = 0;
		int minY, maxY, minX, maxX;
		
		minY = Math.min(p1.y, p2.y);
		maxY = Math.max(p1.y, p2.y);		
		minX = Math.min(p1.x, p2.x);
		maxX = Math.max(p1.x, p2.x);
		
		for(int i = minY; i <= maxY; i++) {
			for(int j = minX; j <= maxX; j++) {
				if(arr[i][j] == ch) result++;
			}
		}
		return result;	
	}
	
	public static boolean isDotsSquaredAndInCorner(Point p1, Point p2, char[][] arr, int dotCount) {		
		if(p1 == null || p2 == null) return false;
		int minY, maxY, minX, maxX;
		
		minY = Math.min(p1.y, p2.y);
		maxY = Math.max(p1.y, p2.y);		
		minX = Math.min(p1.x, p2.x);
		maxX = Math.max(p1.x, p2.x);

		int dp[][] = new int[arr.length][arr[0].length];

		for(int j = minX; j <= maxX; j++) {
			if(arr[minY][j] == '.') dp[minY][j] = 1;
		}
		
		for(int i = minY; i <= maxY; i++) {
			if(arr[i][minX] == '.') dp[i][minX] = 1;
		}
		
		
		for(int i = minY + 1; i <= maxY; i++) {
			for(int j = minX + 1; j <= maxX; j++) {
				dp[i][j] = arr[i][j] == '#' ? 0 : min3(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1;
			}
		}
		
		int max = 0;
		for(int i = minY; i <= maxY; i++) {
			for(int j = minX; j <= maxX; j++) {
				max = Math.max(max, dp[i][j]);
			}
		}
		
		boolean isDotsSquared = false;
		if(max * max == dotCount) isDotsSquared = true;
				
		boolean isDotsInCorner = false;
		if(arr[minY][minX] == '.') isDotsInCorner = true;
		if(arr[maxY][minX] == '.') isDotsInCorner = true;
		if(arr[minY][maxX] == '.') isDotsInCorner = true;
		if(arr[maxY][maxX] == '.') isDotsInCorner = true;		
		
		if(isDotsSquared && isDotsInCorner) {
			return true;
		}
		
		return false;
	}
	
	public static int min3(int a, int b, int c) {
		return Math.min(a, Math.max(b, c));
	}
	
	public static boolean isSquareNumber(int N){
		for(int i = 1; i*i <= N; i++) {
			if(i*i == N) return true;
		}
		
		return false;
	}
	
	static class Point {
		int y, x;	
		
		Point(int y, int x){
			this.y = y;
			this.x = x;
		}				
	}
}