[Codeforces Round #817 (Div. 4)] F. L-shapes

 

---

※. 조건을 만족할 수 있는 입력이 들어왔는지 확인한다.

(L모양이 서로 붙어있는지 확인)

  1. L모양은 꼭짓점을 중심으로 정사각형이 위아래로 1개, 좌우로 1개씩 있어야한다.

  2. arr[i][j]가 * 일 때 상하좌우 *의 개수를 구한다. 이 때 상하 또는 좌우의 * 개수가 2개 이상이면 L모양이 붙어있다는 뜻이 므로 조건을 만족할 수 없다.

  3. L모양이 정상적으로 들어왔다면 각 L모양에 번호를 붙여준다. (계단식으로 L모양이 오는 것도 걸러야함)

(대각선 탐색할 때 구분, 정상적인 L모양인지 구분)

 

※. L모양이 아닌 다른 모양인지 확인, corner에 인접하는 L모양이 있는지 확인한다.

  1. arr[i][j]가 *일때 L모양의 번호가 없다면 no 출력(정사각형 한 칸, 두 칸, 네 칸)

  2. L모양의 모든 *(정사각형 한 칸) 들은 상하좌우 대각선을 포함한 모든 칸에 다른 번호의 *이 있으면 안된다.

     (x배열 {-1,0,1} y배열 {-1,0,1}을 만들어 탐색)

  3. 기존의 번호를 중심으로 탐색할 때 탐색한 번호가 0이 아니고(번호가 있는 *) 탐색한 번호와 기존의 번호가 다르다면 no를 출력

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
//4
public class Main {
	static int[] dx = {-1,0,1};
	static int[] dy = {-1,0,1};
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			boolean answer = false;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			char[][] arr = new char[n][m];
			
			for(int i = 0; i < n; i++) {
				String str = br.readLine();
				for(int j = 0; j < m; j++) {
					arr[i][j] = str.charAt(j);
				}
			}
			
			int curr = 1;
			int[][] id = new int[n][m];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(answer)
						break;
					
					if(arr[i][j] == '*') {
						ArrayList<Integer> tx = new ArrayList<>();
						ArrayList<Integer> ty = new ArrayList<>();
						
						if(i > 0 && arr[i-1][j] == '*') {
							tx.add(i-1);
							tx.add(j);
						}
						if(i < n-1 && arr[i+1][j] == '*') {
							tx.add(i+1);
							tx.add(j);
						}
						if(j > 0 && arr[i][j-1] == '*') {
							ty.add(i);
							ty.add(j-1);
						}
						if(j < m-1 && arr[i][j+1] == '*') {
							ty.add(i);
							ty.add(j+1);
						}
						
						if(tx.size() == 2 && ty.size() == 2) {
							
							if(id[i][j] == 0)
								id[i][j] = curr;
							else
								answer = true;
							
							if(id[tx.get(0)][tx.get(1)] == 0)
								id[tx.get(0)][tx.get(1)] = curr;
							else
								answer = true;
							
							if(id[ty.get(0)][ty.get(1)] == 0)
								id[ty.get(0)][ty.get(1)] = curr;
							else
								answer = true;
							
							curr++;
						}
						else if(tx.size() > 2 || ty.size() > 2) {
							answer = true;
							break;
						}
					}
				}
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(answer)
						break;
					
					if(arr[i][j] == '*') {
						if(id[i][j] == 0) {
							answer = true;
							break;
						}
						
						for(int x = 0; x < 3; x++) {
							for(int y = 0; y < 3; y++) {
								int adx = i+dx[x];
								int ady = j+dy[y];
								if(adx >= 0 && adx < n && ady >= 0 && ady < m) {
									if(id[adx][ady] != id[i][j] && id[adx][ady] != 0) {
										answer = true;
									}
								}
							}
						}
					}
				}
			}
			
			if(answer)
				sb.append("NO").append('\n');
			else
				sb.append("YES").append('\n');
		}
		System.out.println(sb);
 	}
}