3279:Fliptile

keyword

BruteForce　C++

概要

ボード(15*15以下)が与えられて、各セルは黒か白である。あるセルを選ぶとそのセル及び隣接するセルがフリップする。フリップの回数が最小のものを出力せよ。最小回数のものが複数あるときは辞書順最小のものを答えよ。
よくある問題。一番左の列を決めれば後は決まるので左の列に関してBruteForceすればよい。問題は辞書順最小。vectorで比較していたらTLEになったのでcharにしてstrcmpで丁寧に比較したら通った。

bool board[20][20];
bool flipped[20][20];
int h, w;
int dx[] = {0,1,0,-1,0}, dy[] = {0,0,1,0,-1};


int main(){
    int x, i, j, k, mask, best=1<<10, cnt;
    scanf("%d%d",&h,&w);
    REPONE(i,h)REPONE(j,w){
        scanf("%d",&x);
        board[i][j] = x?true:false;
    }
    char ans[h][w+1];
    char tmp[h][w+1];
    REP(i,h)REP(j,w+1)ans[i][j]=(j==w)?'\0':'1';
    REP(mask,1<<w){
        cnt = 0;
        REPONE(i,h)REPONE(j,w)flipped[i][j] = board[i][j];
        REP(j,w)if(mask & (1<<j)){
            cnt++;
            tmp[0][j]='1';
            REP(k,5) flipped[1+dy[k]][j+1+dx[k]] = !flipped[1+dy[k]][j+1+dx[k]];
        }else tmp[0][j]='0';
        REP(i,h)tmp[i][w]='\0';
        for(i=2;i<=h;i++)REPONE(j,w){
            if(flipped[i-1][j]){
                cnt++;
                tmp[i-1][j-1]='1';
                REP(k,5){
                    flipped[i+dy[k]][j+dx[k]] = !flipped[i+dy[k]][j+dx[k]];
                }
            }
            else tmp[i-1][j-1]='0';
        }

        REPONE(i,h)REPONE(j,w)if(flipped[i][j])break;
        if(i==h+1 && j==w+1 && cnt <= best){
            if(cnt < best){
                REP(k,h)strcpy(ans[k],tmp[k]);
                best = cnt;
            }
            else {
                bool f=false;
                REP(k,h){
                    if(f) strcpy(ans[k],tmp[k]);
                    else if(strcmp(ans[k],tmp[k]) > 0){
                        f=true;
                        strcpy(ans[k],tmp[k]);
                    }
                    else break;
                }
            }
        }
    }

    if(best<(1<<9)){
        REP(i,h){
            REP(j,w){
                printf("%c",ans[i][j]);
                if(j<w-1)printf(" ");
            }
            printf("\n");
        }
    }
    else{
        printf("IMPOSSIBLE\n");
    }
    return 0;
}