파핑파핑지뢰찾기

문제

‘파핑 파핑 지뢰 찾기’라는 유명한 게임이 있다. 이 게임은 RXC 크기의 표를 이용하는 게임인데,

표의 각 칸에는 지뢰가 있을 수도 있고 없을 수도 있다.

표의 각 칸을 클릭했을 때, 그 칸이 지뢰가 있는 칸이라면 ‘파핑 파핑!’이라는 소리와 함께 게임은 끝난다.

지뢰가 없는 칸이라면 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 최대 8칸에 대해 몇 개의 지뢰가 있는지가 0에서 8사이의 숫자로 클릭한 칸에 표시된다.

만약 이 숫자가 0이라면 근처의 8방향에 지뢰가 없다는 것이 확정된 것이기 때문에 그 8방향의 칸도 자동으로 숫자를 표시해 준다.

실제 게임에서는 어떤 위치에 지뢰가 있는지 알 수 없지만, 이 문제에서는 특별히 알 수 있다고 하자.

지뢰를 ‘*’로, 지뢰가 없는 칸을 ‘.’로, 클릭한 지뢰가 없는 칸을 ‘c’로 나타냈을 때 표가 어떻게 변화되는지 나타낸다.

세 번째 예에서는 0으로 표시 될 칸들과 이와 인접한 칸들이 한 번의 클릭에 연쇄적으로 숫자가 표시된 것을 볼 수 있다.

파핑 파핑 지뢰 찾기를 할 때 표의 크기와 표가 주어질 때, 지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번의 클릭을 해야 하는지 구하는 프로그램을 작성하라.

package a1001;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

import a1001.인구이동.Pair;

public class 파핑파핑지뢰찾기 {

	static int T;
	static int n;
	static char[][]arr;
	
	static int[] dx = {-1,1,0,0,-1,-1,1,1};
	static int[]dy = {0,0,-1,1,1,-1,1,-1};
	static int[] lx = {-1,1,0,0};
	static int[] ly = {0,0,-1,1};
	static int[][]nums;
	public static boolean cango(int x, int y) {
		
		return x>=0 && x<n && y>=0 &&y<n;
	}
	
	public static void print() {
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				
				System.out.print(nums[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
		
	}

	public static boolean checkAll() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				
				if(arr[i][j]=='.'&&nums[i][j]==-1) { //숫자부분인데 아직 파핑이 안됐을 경우 
					return false;
				}
				
			}
		}
		return true;
		
	}
	
	static class Pair{
		int x,y;
		Pair(int x, int y){
			this.x=x;
			this.y = y;
		}
		
	}

	public static void bfs( boolean[][]check,  int i, int j) {
		
			Queue<Pair>q = new LinkedList<>();
			q.add(new Pair(i, j));
			check[i][j]=true;
			
			while(!q.isEmpty()) {
				
				Pair p = q.poll();
				int x = p.x;
				int y = p.y;
				
				int count=0;
				
				for(int t=0; t<8; t++) {
					
					int nx = x+dx[t];
					int ny = y+dy[t];
					
					if(cango(nx,ny) && arr[nx][ny]=='*') {
						count++;
					}
					
					
				}
				if(arr[x][y]=='.') {
					nums[x][y]=count;
				
				}
				
				for(int t=0; t<4; t++) { //주변 4방향만 탐색 
					
					int nx = x+lx[t];
					int ny = y+ly[t];
					
					if(cango(nx,ny)&& !check[nx][ny]) {
						
						q.add(new Pair(nx,ny));
						check[nx][ny]=true;
					
					}
					
					
				}
			}
		

	}
	
	
	public static void dfs2( boolean[][]check,  int i, int j) {
		
		
		
		int count=0;
		
		for(int t=0; t<8; t++) {
			
			int nx = i+dx[t];
			int ny = j+dy[t];
			
			if(cango(nx,ny) && nums[nx][ny]>=0 && !check[nx][ny]) {
				
				
				check[nx][ny]=true;
				
				if(nums[nx][ny]==0) {
				dfs2(check,nx,ny);
				}
			}
		}
	
		
		
}
	

	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		T= Integer.parseInt(br.readLine());
	
		for(int test_case = 1; test_case <= T; test_case++)
		{
			n = Integer.parseInt(br.readLine());
			arr = new char[n][n];
			
			for(int i=0; i<n; i++) {
				String s = br.readLine();
				for(int j=0; j<n; j++) {
					
					arr[i][j] = s.charAt(j);
				}
				
				
			}
			
			nums = new int[n][n];
			
			for(int i=0; i<n; i++) {
				
				for(int j=0; j<n; j++) {
					nums[i][j]=-1; //모든 부분을 -1로 만든다
				}
			}
			
			boolean[][] check2 = new boolean[n][n];
			check2[0][0]=true;
			bfs(check2,0,0); //bfs로 숫자를 쓸 수 있는 곳에 모두 숫자를 써준다.
			
			boolean[][] check = new boolean[n][n];
			int answer=0;
			
			
			//최솟값을 얻기 위해선 0먼저 파핑을 시켜야한다
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					
					if(nums[i][j]==0 && check[i][j]==false) { //아직 파핑이 되지 않은 부분이 있을때
						check[i][j]=true;
						dfs2(check,i,j); //0인경우 주변의 8방향을 파핑 그리고 주변에 다른 0도 연쇄적으로 파핑
						answer++;
					}
					
				}
			}
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					
					if(nums[i][j]>0 && check[i][j]==false) { //0이 아니라서 파핑이 안된 부분을 모두 하나하나 파핑하도록한다
						answer++;
					}
					
				}
			}

			System.out.println("#"+test_case+" "+answer);
		
			
		}
		
	}
	
	
}