14413. 격자판 칠하기 JAVA

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYEXgKnKKg0DFARx&categoryId=AYEXgKnKKg0DFARx&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;

public class SWEA14413 {
	public static final char WHITE = '.';
	public static final char BLACK = '#';
	public static int N;
	public static int M;
	public static final int[] X_EWSN = {0, 0, 1, -1};
	public static final int[] Y_EWSN = {1, -1, 0, 0};
	public static boolean isImpossible = false;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			List<Integer> x_arr = new ArrayList<Integer>();
			List<Integer> y_arr = new ArrayList<Integer>();
			
			char[][] map = new char[N][M];
			isImpossible = false;
			
			for (int x=0; x<N; x++) {
				String line = br.readLine();
				
				if (isImpossible) {
					continue;
				}
				
				for (int y=0; y<M; y++) {
					char elem = line.charAt(y);
					map[x][y] = elem;
					boolean checkElem = judgeEWSN(map, x, y, elem);
					if (!checkElem) {
						isImpossible = true;
						break;
					}
					
					if (elem == '?') {
						x_arr.add(x);
						y_arr.add(y);
					}
				}
			}
			
			if (isImpossible) {
				System.out.printf("#%d impossible\n", test_case);
			} else {
				isImpossible = true;
				makeMap(map, x_arr, y_arr, 0);	
				
				if (isImpossible) {
					System.out.printf("#%d impossible\n", test_case);	
				} else {
					System.out.printf("#%d possible\n", test_case);
				}
			}
		}
	}
	
	public static void makeMap(char[][] map, List<Integer> x_arr, List<Integer> y_arr, int cnt) {
		if (x_arr.size() <= cnt) {
			isImpossible = false;
			return;
		}
		
		char[][] new_map = new char[N][M];
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				new_map[i][j] = map[i][j];
			}
		}
		
		int x_value = x_arr.get(cnt);
		int y_value = y_arr.get(cnt);
		
		boolean result = judgeEWSN(new_map, x_value, y_value, WHITE);
		if (result) {
			new_map[x_value][y_value] = WHITE;
			makeMap(new_map, x_arr, y_arr, cnt+1);
		}
		
		result = judgeEWSN(new_map, x_value, y_value, BLACK);
		if (result) {
			new_map[x_value][y_value] = BLACK;
			makeMap(new_map, x_arr, y_arr, cnt+1);
		}
	}
	
	public static boolean judgeEWSN(char[][] map, int x, int y, int value) {
		if (value == '?') {
			return true;
		}
		
		for (int i = 0; i < 4; i++) {
			int a = x + X_EWSN[i];
			int b = y + Y_EWSN[i];
			
			
			if (a>=0 && a<N && b>=0 && b < M) {
				if (map[a][b] == value) {
					return false;
				}
			}
		}
		
		return true;
	}
}