ID : BOARDCOVER 난이도 : 하 (재귀 완전탐색)

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

#include <iostream>
#include <vector>
#include <string>
 
class Board
{
public:
    const int COVER_TYPE[4][3][2] = {
        { { 0, 0 },{ 1, 0 },{ 0, 1 } },    //type1
        { { 0, 0 },{ 0, 1 },{ 1, 1 } },    //type2
        { { 0, 0 },{ 1, 0 },{ 1, 1 } },    //type3
        { { 0, 0 },{ 1, 0 },{ 1, -1 } }    //type4
    };
 
    int mnHeight;
    int mnWidth;
    int mnAvailableCount;
    int mnZeroCount;
    std::vector<std::vector<int>> mBoardVector;
    //std::vector<std::string> mBoadrVector;
 
    void CountAvailableSet();
 
private:
    bool _Set(std::vector<std::vector<int>>& parBoard, int parY, int parX, int parType, int parDelta);
    int _Cover(std::vector<std::vector<int>>& parBoard);
 
 
};
 
 
int main()
{
    int nTestCase;
    std::vector<Board> boardList;
 
    boardList.clear();
    std::cin >> nTestCase;
    getchar();
    if (nTestCase > 30)
        return -1;
 
    for (int i = 0; i < nTestCase; ++i)
    {
        Board tmpBoard;
        int nCount = 0;
 
        tmpBoard.mBoardVector.clear();
        std::cin >> tmpBoard.mnHeight >> tmpBoard.mnWidth;
        getchar();
 
        if (tmpBoard.mnHeight < 1 || tmpBoard.mnWidth > 20)
            return -1;
 
        for (int j = 0; j < tmpBoard.mnHeight; ++j)
        {
            std::vector<int> tmpBoardList;
            std::string strTmpBoardLine;
 
            tmpBoardList.clear();
            std::getline(std::cin, strTmpBoardLine);
 
            for (int k = 0; k < strTmpBoardLine.size(); ++k)
            {
                if (strTmpBoardLine[k] == '#')
                {
                    tmpBoardList.push_back(1);
                }
                else if (strTmpBoardLine[k] == '.')
                {
                    tmpBoardList.push_back(0);
                    nCount++;
                }
            
            }
            tmpBoard.mBoardVector.push_back(tmpBoardList);
            tmpBoard.mnZeroCount = nCount;
            if (nCount > 50)
                return -1;
        }
 
        boardList.push_back(tmpBoard);
    }
    
    for (auto& board : boardList)
    {
        board.CountAvailableSet();
        std::cout << board.mnAvailableCount << std::endl;
    }
 
 
    return 0;
}
 
void Board::CountAvailableSet()
{
    
    if ((mnZeroCount % 3) != 0)    //3의 배수가 아닌 빈칸은 의미없다.
    {
        mnAvailableCount = 0;
    }
    else
    {
        mnAvailableCount = _Cover(mBoardVector);
    }
 
}
 
bool Board::_Set(std::vector<std::vector<int>>& parBoard, int parY, int parX, int parType, int parDelta)
{
    bool isOk = true;
    for (int i = 0; i < 3; ++i)
    {
        //각 타입별 3개의 좌표 입력
        const int nY = parY + COVER_TYPE[parType][i][0];
        const int nX = parX + COVER_TYPE[parType][i][1];
 
 
        if (nY < 0 || nY >= mnHeight || nX < 0 || nX >= mnWidth)    //각 좌표의 범위체크
        {
            isOk = false;
        }
        else if ((parBoard[nY][nX] += parDelta) > 1)    // 각 좌표를 채우고
        {                                                // 검은칸 또는 이미 채워진 곳인지 확인
            isOk = false;
        }
    }
    return isOk;
}
 
 
//parBoard의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
//parBoard[i][j] = 1 이면 이미 덮인 칸 혹은 검은 칸
//parBoard[i][j] = 0 이면 아직 덮이지 않은 칸
int Board::_Cover(std::vector<std::vector<int>>& parBoard)
{
    //아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
    int nY = -1;
    int nX = -1;
    for (int i = 0; i < parBoard.size(); ++i)
    {
        for (int j = 0; j < parBoard[i].size(); ++j)
        {
            if (parBoard[i][j] == 0)
            {
                nY = i;
                nX = j;
                break;
            }
        }
        if (nY != -1) break;
    }
 
    //기저 사례 : 모든 칸을 채웠으면 1을 반환한다.
    if (nY == -1) return 1;
    int ret = 0;
 
    for (int type = 0; type < 4; ++type)
    {
        //만약 parBoard[y][x]를 type형태로 덮을 수 있으면 재귀 호출한다.
        if(_Set(parBoard, nY, nX, type, 1))
        {
            ret += _Cover(parBoard);
        }
        //덮었던 블록을 치운다.
        _Set(parBoard, nY, nX, type, -1);
    }
    return ret;
}