게임판 덮기 - Brute Force

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int testCase = Integer.parseInt(br.readLine());

        for(int t=0; t<testCase; t++) {
            int h,w;
            int[][] matrix;
            int count = 0;
            st = new StringTokenizer(br.readLine()," ");
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            matrix = new int[h][w];
            for(int i=0; i<h; i++) {
                String str = br.readLine();
                for(int j=0; j<w; j++) {
                    if(str.charAt(j) == '#') { matrix[i][j] = 0; }
                    else { matrix[i][j] = 1; count++; }
                }
            }

            int answer = 0;
            if(count % 3 == 0) answer = f(matrix);
            System.out.println(answer);
        }
    }

    static int f(int[][] matrix) {
        int[][][] coverType = {
                {{0, 0}, {1, 0}, {0, 1}},
                {{0, 0}, {0, 1}, {1, 1}},
                {{0, 0}, {1, 0}, {1, 1}},
                {{0, 0}, {1, 0}, {1,-1}}
        };

        boolean check = true;
        int x=0, y=0;
        for(int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[i].length; j++)
                if (matrix[i][j] == 1) {
                    check = false;
                    x = i;
                    y = j;
                    break;
                }
            if(!check) break;
        }
        if(check) return 1;

        int count = 0;
        for(int i=0; i<4; i++) {
            boolean next = true;
            for(int j=0; j<3; j++) {
                int new_x = x + coverType[i][j][0];
                int new_y = y + coverType[i][j][1];
                if(new_x < 0 || new_x >= matrix.length || new_y < 0 || new_y >= matrix[0].length || matrix[new_x][new_y] == 0) {
                    next = false;
                }
            }

            if(next) {
                for(int j=0; j<3; j++) {
                    int new_x = x + coverType[i][j][0];
                    int new_y = y + coverType[i][j][1];
                    matrix[new_x][new_y] = 0;
                }
                count += f(matrix);
                for(int j=0; j<3; j++) {
                    int new_x = x + coverType[i][j][0];
                    int new_y = y + coverType[i][j][1];
                    matrix[new_x][new_y] = 1;
                }
            }
        }
        return count;
    }
}