[알고스팟] BOARDCOVER - java

https://algospot.com/judge/problem/read/BOARDCOVER

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BOARDCOVER
  • 2000ms
  • 65536kb
  • 5284
  • 2463 (46%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

입력

력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, .는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

---

쉬운 문제이다.

얼핏보면 어려워 보이지만

정답은 Full Scan 방식으로 겁나 쉬운 문제

특이점은 값 범위를 초과하지 않도록, 그뭐냐 board를 그릴떄 #으로 한번 더 감싸주었다.

이론은 알고있었지만 적용해본건 처음이엇는데

생각보다 엄청 헷갈려서 결국 손코딩 후 재작업 ㅠㅠㅠㅠㅠㅠ

PICNIC과 같이 재귀함수를 이용하면 된다.

package algoSpot.BOARDCOVER;

import java.util.Arrays;

/**
 * Created by eunbi on 2018-02-06.
 */
public class BOARDCOVER_EB {
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static java.util.Scanner sc = new java.util.Scanner(System.in);
    public static int C;
    public static int H;
    public static int W;
    public static int count =0;

    public static String[][] board;
    public static void main(String[] args)throws Exception {
        C=Integer.parseInt(br.readLine().trim());

        for(int i=0;i<C;i++) {
            solve();
        }
        System.out.println(sb.toString());
    }

    public static void solve()throws Exception {
//        H=8;
//        W=10;
        String lines = br.readLine();
        String[] spl  = lines.split(" ");
        H=Integer.parseInt(spl[0]);
        W=Integer.parseInt(spl[1]);


/*        String input = "########## \n" +
                "#........# \n" +
                "#........# \n" +
                "#........# \n" +
                "#........# \n" +
                "#........# \n" +
                "#........# \n" +
                "########## ";

        String[] lines = input.split("\n");*/

        initBoard();


        /**
         * Data Setting
         */
        for(int i=0;i<H;i++){
            String input = br.readLine();
            int j=1;
            for(char c : input.toCharArray()){
                board[i+1][j] = String.valueOf(c);
                j++;
            }

        }

        boardCover();
        sb.append(count).append("\n");
    }

    public static void boardCover(){
        /**
         * Find first point '.'
         */
        int x=1;
        int y=1;
        for(x=1;x<H+1;x++){
            for(y = 1; y < W+1; y++) {
                if (board[x][y].equals(".")) {
                    break;
                }
            }
            if (y<W+1&&board[x][y].equals(".")) {
                break;
            }
        }

        //기저
        if(x == H+1 && y == W+1){
            count++;
            return ;
        }

        // *
        // @ @
        if(board[x+1][y].equals(".")&&board[x+1][y+1].equals(".")){
            board[x][y] = board[x+1][y] =board[x+1][y+1] = "*";
            boardCover();
            board[x][y] = board[x+1][y] =board[x+1][y+1] = ".";
        }
        // *
        //@@
        if(board[x+1][y-1].equals(".")&&board[x+1][y].equals(".")){
            board[x][y] = board[x+1][y-1] =board[x+1][y] = "*";
            boardCover();
            board[x][y] = board[x+1][y-1] =board[x+1][y] = ".";
        }
        // *@
        //  @
        if(board[x][y+1].equals(".")&&board[x+1][y+1].equals(".")){
            board[x][y] = board[x][y+1] =board[x+1][y+1] = "*";
            boardCover();
            board[x][y] = board[x][y+1] =board[x+1][y+1] = ".";
        }
        // *@
        // @
        if(board[x+1][y].equals(".")&&board[x][y+1].equals(".")){
            board[x][y] = board[x+1][y] =board[x][y+1] = "#";
            boardCover();
            board[x][y] = board[x+1][y] =board[x][y+1] = ".";
        }

    }

    public static String printBoard(){
        StringBuilder sb = new StringBuilder();
        sb.append("==========================\n");
        for(int x=0;x<H+2;x++){
            for(int y = 0; y < W+2; y++) {
                sb.append(board[x][y]+" ");

            }

            sb.append("\n");
        }
        sb.append("==========================\n");
        System.out.println(sb.toString());
        return sb.toString();
    }
    public static void initBoard(){
        //3 , 7
        board = new String[H+2][W+2];
        for(int i=1;i<=H;i++){
            board[i][0] = board[i][W+1] = "#";
        }
        for(int i=0;i<W+2;i++){
            board[0][i] = board[H+1][i] = "#";
        }
        count=0;
    }
}