2458:Rigging the Bovine Election

keyword

BruteForce　C++

概要

5*5のボードが与えられて、各セルはHかJである。連続する7つのセルで、Jが4つ以上あるような選び方は何通りあるか求める問題。
(25,7)は4*10^6位なので全探索が間に合うはず。連続しているかどうかはBFSで判定。手元で最大ケース(全部J)を試すと約60msなので余裕と思って提出すると謎のTLE。いろいろいじっている内にTime Limitギリギリの1000msで通った。あれ絶対複数ケース試してるよね…

int ps[10];
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
char board[27];

inline bool adjCheck(){
    int i,k,visited=~0,pos=0;
    int Q[10];
    Q[pos++] = ps[0];
    REPONE(i,6) visited ^= 1<<ps[i];
    while(pos>0){
        int tp = Q[--pos];
        int y=tp/5, x=tp%5;
        REP(k,4){
            int nx=x+dx[k], ny=y+dy[k];
            if(binary_search(ps,ps+7,5*ny+nx) && 0<=nx && nx<5 && 0<=ny && ny<5 && !(visited & (1<<(5*ny+nx)))){
                Q[pos++] = 5*ny+nx;
                visited ^= 1<<(5*ny+nx);
            }
        }
    }
    return visited==~0;
}

inline bool countJ(){
    int ret = 0, i;
    REP(i,7)if(board[ps[i]] == 'J') ret++;
    return ret>=4;
}

int main(){
    int i,j,bits[27],cnt=0;
    char str[7];

    REP(i,5){
        scanf("%s\n",str);
        REP(j,5) board[i*5+j] = str[j];
    }

    REP(i,25)bits[i] = (i<7)?1:0;

    do{
        int pos = 0;
        REP(i,25)if(bits[i])ps[pos++] = i;
        if(countJ() && adjCheck()) cnt++;
    }while(prev_permutation(bits,bits+25));

    printf("%d\n",cnt);

    return 0;
}