[algospot] BLOCKGAME

문제링크 입니다

[BLOCKGAME] 문제 😭😭😭😭😭

시티빌과 비주얼드에 지친 진호와 현환이는 집에 굴러다니는 블럭들을 모아 새로운 게임을 하기로 했습니다. 5×5 크기의 게임판에서 시작해, 둘이 번갈아 가며 블럭을 하나씩 게임판에 내려놓습니다. 블럭은 L 모양으로 구성된 3칸짜리 블럭과 2칸짜리 블럭이 있으며, 항상 게임판에 있는 줄에 맞춰 내려놓아야 합니다. 블럭들은 서로 겹칠 수 없습니다. 다음 그림은 진행중인 게임판의 모습을 보여줍니다.

그림에서 보이는 바와 같이 각 블록은 자유롭게 뒤집거나 회전해서 올려놓을 수 있습니다. 두 사람이 번갈아가며 블록을 올려놓다가 더 올려놓을 수 없게 되면 마지막에 올려놓은 사람이 승리합니다. 진행 중인 게임판이 주어질 때 이번 차례인 사람이 승리할 수 있는 방법이 있는지를 판단하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C≤50)가 주어집니다. 각 테스트 케이스는 다섯 줄에 각 다섯 개의 문자로 구성되며, #는 이미 블록이 놓인 칸, 마침표(.)는 블록이 없는 칸을 의미합니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 이번 차례인 사람이 항상 이길 수 있는 방법이 있다면 WINNING을, 항상 질 수밖에 없다면 LOSING을 출력합니다.

입력 예제

3
.....
.##..
##..#
#.###
..#..
.....
.....
.....
.....
.....
#..##
##.##
##.##
#...#
##.##

출력 예제

WINNING
LOSING
WINNING

전체 코드는 다음과 같습니다.

//
//  BLOCKGAME.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/15.
//

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin("BLOCKGAME.txt");
vector<int> moves;
inline int cell(int y, int x){ return 1 << (y*5 + x); }
void preCalc(){
    //ㄱ 자 모양
    for(int y=0; y<4; y++){
        for(int x=0; x<4; x++){
            vector<int> cells;
            for(int dy=0; dy<2; dy++){
                for(int dx =0 ; dx<2; dx++){
                    cells.push_back(cell(y+dy,x+dx));
                }
            }
            int squares = cells[0] + cells[1] +cells[2] +cells[3];
            for(int i=0; i< 4; i++){
                moves.push_back(squares - cells[i]);
            }
        }
    }
    //1자 모양
    for(int i=0; i<5; i++){
        for(int j=0; j<4; j++){
            moves.push_back(cell(i,j)+cell(i,j+1));
            moves.push_back(cell(j,i)+cell(j+1,i));
        }
    }
}
char cache[1<< 25];
// 현재 게임판 상태가 board일때 현재 차례인 사람이 승리할지 여부를 반환한다.
// (y,x) 칸에 블록이 있다. <=> (y*5 +x) 번 비트가 있다.
int play(int board){
    char &ret = cache[board];
    if(ret!= -1) return ret;
    ret = 0;
    for(int i=0; i< moves.size(); i++){
        //이 수를 게임판에 놓을 수 있는가.
        if((moves[i] & board) == 0){
            // 다음수를 못 놓는다면
            if(!play(board | moves[i])){
                ret = 1;
                break;
            }
        }
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;

    for(int i = 0; i < test_case; i++){
        preCalc();
        memset(cache, -1, sizeof(cache));
        char space=0;
        int board=0;
        for(int j=0; j<5; j++){
            for(int k=0; k<5; k++){
                fin >> space;
                if(space =='#'){
                    board |= cell(j,k);
                }

            }
        }

        cout << (play(board) ? "WINNING" : "LOSING") << endl;
    }
    return 0;
}