알고리즘 문제해결전략 문제6.5 게임판 덮기(ID: BOARDCOVER)

 

#include <iostream>
#include <vector>
using namespace std;
int cnt;
const int coverType[4][3][2] = {
    {{0,0}, {0,1}, {1,1}},    // 블록이 회전하는 4가지 형태 
    {{0,0}, {1,0}, {1,1}},
    {{0,0}, {1,0}, {1,-1}},
    {{0,0}, {0,1}, {1,0}}
};
bool set(vector<vector<int> >& board, int y, int x, int type, int delta)
{
    bool state = true;
    for (int i = 0; i < 3; i++)
    {
        int colMax = board.size();
        int rowMax = board[0].size();
        const int ny = y + coverType[type][i][0];
        const int nx = x + coverType[type][i][1];
        if (ny < 0 || ny >= colMax ||
            nx < 0 || nx >= rowMax)
            state = false;
        else if ((board[ny][nx] += delta) > 1)    // delta = 1 일 때, 블록을 덮는다. 
            state = false;                        // delta = -1 일 때, 블록을 치운다. 
    }
    return state;
}
int Solution(vector<vector<int> >& board)
{
    if (cnt % 3 != 0) return 0;    // 기저 사례. 비어이는 블록의 수가 3의 배수가 아닐 경우 반드시 실패
    int col = -1, row = -1;
    int colMax = board.size();    // 행 길이
    int rowMax = board[0].size();    // 열 길이
    for (int i = 0; i < colMax; i++)
    {
        for (int j = 0; j < rowMax; j++)    // 비어있는 칸 중 좌측 상단을 먼저 
        {
            if (board[i][j] == 0)
            {
                col = i;
                row = j;
                break;
            }
        }
        if (col != -1) break;    // 2중 for문 탈출 
    }
    if (col == -1) return 1;    // 기저 사례. 비어있는 칸이 없으므로 1 증가
    int ret = 0;
    for (int i = 0; i < 4; i++)
    {
        if (set(board, col, row, i, 1))    // 비어있는 칸에 블록을 맞춰본다 
            ret += Solution(board);
        set(board, col, row, i, -1);
    }
    return ret;
}
int main(void)
{
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int a, b;
        cin >> a >> b;
        vector<vector<int>> board(a);
        cnt = 0;
        for (int i = 0; i < a; i++)
        {
            for (int j = 0; j < b; j++)
            {
                char block;
                cin >> block;
                if (block == '#')    // 막힌 칸을 1로 치환 
                    board[i].push_back(1);
                else if (block == '.')    // 비어있는 칸을 0으로 치환 
                {
                    board[i].push_back(0);
                    cnt++;
                }
            }
        }
        cout << Solution(board) << endl;
        board.clear();
    }
    return 0;
}

 

 

 

알고리즘 200일 프로젝트 - 4day

알고리즘 문제해결 전략 6.5 게임판 덮기(ID:BOARDCOVER)

피크닉 문제에서 적용한 재귀함수와 유사한 형태로 구현할 수 있는 문제였다.

내가 생각한 아이디어와 책에서 제시한 아이디어의 접근방법은 비슷했으나,

중복을 신경쓰지 못하여 원하는 출력을 얻지 못하였다. 꾸준히 복습하여 내것으로 만들도록 해야겠다. 

내일도 열심히!