BLOCKGAME 질문합니다

  • kws4679
    kws4679

    BLOCKGAME 문제 자꾸 타임아웃이 나와서 질문드립니다

    문제를 푼 방식은 다음과 같습니다.

    책의 방식과 다르지않다고 생각하는데요

    일단 처음에 모든 블락의 위치를 pre[i][j][블락종류]

    배열에 저장합니다. 그리고

    canwin(state) 은 현재 사람이 이기고 지는것을

    true,false 로 반환합니다.

    불리는 횟수를 재보니까 2백만개정도 불리더군요

    동적계획법을 썼음에도 불구하고 이렇게 시간초과가 나오는데

    어떻게 방법이 없을까요??

    책을 봐도 비슷한 방식으로 풀은것 같습니다만 ㅠㅠ

    어쨌든 코드도 첨부해봅니다!!

    #include <iostream>
#include <cstring>
using namespace std;
int block[6][3][2] = {{{0,0},{0,1},{0,0}},{{0,0},{1,0},{0,0}},{{0,0},{1,0},{0,1}},{{0,0},{0,1},{1,1}},{{1,0},{0,1},{1,1}},{{0,0},{1,0},{1,1}}};
int pre[5][5][6];
char cache[1<<25];
int set(int i,int j, int to, int state){
    return state | to << (i*5+j);
}
int put(int i, int j, int k, int state){
    int ret;
    for(int m=0;m<3;++m){
        if(i+block[k][m][0] >= 5 || j+block[k][m][1] >= 5) return ret = -1;
        if(state & 1 << ((i+block[k][m][0])*5 + j+block[k][m][1])) return ret = -1;
    }
    for(int m=0;m<3;++m)
        state = set(i+block[k][m][0], j+block[k][m][1], 1, state);
    return state;
}
char canwin(int state) {
    char& ret = cache[state];
    if(ret != -1) return ret;
    for(int i=0;i<5;++i)
        for(int j=0;j<5;++j){
            for(int k=0;k<6;++k){
                if(pre[i][j][k] == -1) continue;
                if(state & pre[i][j][k]) continue;
                if(!canwin(state | pre[i][j][k])) return ret = true;
            }
        }
    return ret = false;
}
int main(){
    int c;
    scanf("%d", &c);
    memset(pre, 0, sizeof(pre));
    for(int i=0;i<5;++i)
       for(int j=0;j<5;++j)
            for(int k=0;k<6;++k)
               pre[i][j][k] = put(i,j,k,0);
    while(c--){
        memset(cache, -1, sizeof(cache));
        int state = 0;
        for(int i=0;i<5;++i){
            string t;
            cin >> t;
            for(int j=0;j<5;++j)
                if(t[j]=='#') state = set(i,j,1,state);
        }
        printf(canwin(state)?"WINNING\n":"LOSING\n");
    }
    return 0;
}

    우째 뒤로갈수록 책을 봤음에도 불구하고 질문을 매번

    올리는것 같네요 ㅠㅠ


    11년 전
1개의 댓글이 있습니다.
  • rapguy
    rapguy

    저도 알고리즘책에 있는 그대로 제출했음에도 아무것도 없는 케이스에서 7초이상 걸려서 시간초가가 나왔습니다.

    하지만 char canwin(int state)함수에서 return 하면서 cache 에 값을 적어줄때 추가구현을 하니 pass 되었습니다.

    return 할때의 cache 값을 블록map으로 바꿔준 후에 그 블록을 90도, 180도, 270도, 미러링, 미러링된것을 90도, 180도 270도 맵을 회전시켜 해당 cache 값도 동일한 return 값으로 기록해주면

    return 하면서 cache 에 값을 1번 써줄것을 cache 8개에 써주는 효과로 시간이 빨라집니다.


    10년 전 link

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