BLOCKGAME 틀린곳을... 못찾겠습니다 ㅠㅠ...

  • pica4500
    pica4500

    한번 제 나름대로 코드를 짜봤는데 제 생각이 틀려 오답이 나온것 같아서 다른 분들의 의견을 여쭙고자 합니다.. ㅠㅠ

    twoBlock, threeBlock -> 현재 칸을 포함했다는 전제하에 2칸 3칸 블럭을 놓을수 있는 위치들을 저장

    status -> 이진수로 25칸 배열의 상태를 나타내어 전달함.

    전체적인 알고리즘 설명:

    int game(state):
    1. state를 토대로 판을 재구성
    2. 판에서 새로 놓을수 없다면 패배
    3. 새로 놓을 수 있다면, 가능한 모든 곳들을 두어보며 성공할 수 있는 신의 한수가 있다면 즉시 성공을 리턴
    4. 신의한수가 한번도 없었다면 패배를 리턴

    #include<iostream>
    using namespace std;
    
    char cache[1<<25];
    bool board[5][5];
    int twoBlock[2][2] = { {0, 1}, {1, 0} };//현재칸 포함, 아래칸도 비었거나, 옆에칸도 비었거나
    int threeBlock[3][2][2] = { {{0, 1},{1, 0}}, {{1, 0},{1, 1}}, {{0, 1},{1, 1}} };//현재칸 포함해서 가능한 ㄱ, ㄴ모양들
    
    bool insideBoard(int x, int y) {//경계 밖을 나갔는지 확인
        if (x >= 0 && x < 5 && y >= 0 && y < 5) return true;
        return false;
    }
    bool isLose() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (!board[i][j]) {//판 처음부터 끝까지 2칸짜리나 3칸짜리 블럭을 놓을수 있는지 확인
                    for (int k = 0; k < 2; k++) {
                        int x = i + twoBlock[k][0];
                        int y = j + twoBlock[k][1];
                        if (insideBoard(x, y) && !board[x][y]) return false;
                    }
                    for (int k = 0; k < 3; k++) {
                        int x1 = i + threeBlock[k][0][0];
                        int y1 = j + threeBlock[k][0][1];
                        int x2 = i + threeBlock[k][1][0];
                        int y2 = j + threeBlock[k][1][1];
                        if (insideBoard(x1, y1) && insideBoard(x2, y2) && !board[x1][y1] && !board[x2][y2]) return false;
                    }
                }
            }
        }
        return true;
    }
    
    void makeBoard(int curBoard) {//현재 정보로 판 구성
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                int correct = 1 << (i * 5) + j;
                int flag = correct & curBoard;
                if (flag) board[i][j] = true;
                else board[i][j] = false;
            }
        }
    }
    
    int game(int curBoard) {
        makeBoard(curBoard);//그때 그때 판 재구성
        if (isLose()) return -1;//지금 놓을 수 없다면 전사람이 승리
        char& ret = cache[curBoard];
        if (ret != -2) return ret;
    
        ret = -1;//내가 승리한 경우가 없다면 패배
        for (int i = 0; i < 25; i++) {
            if (((1 << i) & curBoard) == 0) {//현재 칸이 비어있고
                int j = i / 5;
                int k = i % 5;
                if (!board[j][k]) {
                    for (int l = 0; l < 2; l++) {//두개짜리 블록을 놓을 수 있는 경우에 대해서
                        int x = j + twoBlock[l][0];
                        int y = k + twoBlock[l][1];
                        if (insideBoard(x, y) && !board[x][y]) {
                            int add = (1 << i) + (1 << ((x * 5) + y));
                            if(-game(curBoard + add) == 1) return ret = 1;//한번이라도 승리가 가능하면 승리
                        }
                    }
                    for (int l = 0; l < 3; l++) {//세개짜리 블록을 놓을 수 있는 경우에 대해서
                        int x1 = j + threeBlock[l][0][0];
                        int y1 = k + threeBlock[l][0][1];
                        int x2 = j + threeBlock[l][1][0];
                        int y2 = k + threeBlock[l][1][1];
                        if (insideBoard(x1, y1) && insideBoard(x2, y2) && !board[x1][y1] && !board[x2][y2]) {
                            int add = (1 << i) + (1 << ((x1 * 5) + y1)) + (1 << ((x2 * 5) + y2));
                            if(-game(curBoard + add) == 1) return ret = 1;//한번이라도 승리가 가능하면 승리
                        }
                    }
                }
            }
        }
        return ret;//한번도 못이겼으면 패배
    }
    
    int main() {
        int tc;
        cin >> tc;
        while (tc--) {
            for (int i = 0; i < (1 << 25); i++) cache[i] = -2;
            int state = 0;
            for (int i = 0; i < 25; i++) {
                char input;
                cin >> input;
                if (input == '#') state += (1 << i);
            }
            if (game(state) == 1) cout << "WINNING" << endl;
            else cout << "LOSING" << endl;
        }
    }
    

    7년 전
2개의 댓글이 있습니다.
  • Corea
    Corea

    아래 입력을 넣어보세요.

    1
    #####
    #####
    #####
    ####.
    ###..

    7년 전 link
  • pica4500
    pica4500

    헛...!!!!!! 감사합니다 ㅠㅜ


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.