Algoogle

Algorithm for Programming Contest

PKU 3279 Fliptile

Category: PKU Tag: brute-force

Fliptile

問題概要


M*Nのタイルがあり, 1の場所が裏返っている.
牛はあるタイルを選んで裏返すとき上下左右のタイルも裏返してしまう.
最小回数の反転で全て表に出来る時, 各タイルに対して何回反転するかを答えよ.
複数ある場合は文字列として見た時辞書順最小のものを答えよ.

解法


まず, 同じタイルを2回選ぶのは明らかに無駄.
一番上の行の裏返す場所を決めると2行目以降は, その上の行の1になっている部分を裏返さなければならないので一意に定まる.
このあと最後の行がすべて0であればok
よって一番上の行のひっくり返し方を全て試せばよい. ビットでやるのが楽でいい.

コード


(3279.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>

using namespace std;

int N, M, ma, sum;
int table[16][16], ttable[16][16];
int ans[16][16], tans[16][16];

void flip(int i, int j){
    ttable[i][j] ^= 1;
    if(i) ttable[i-1][j] ^= 1;
    if(j) ttable[i][j-1] ^= 1;
    if(i<M-1) ttable[i+1][j] ^= 1;
    if(j<N-1) ttable[i][j+1] ^= 1;
}

void copy_table(){
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            ttable[i][j] = table[i][j];
}

void flip_one(int S){
    for(int j = N-1; S > 0 and j >= 0; j--, S >>= 1)
        if(S&1) {
            tans[0][j] = 1;
            flip(0, j);
        }
}

bool ok(){
    for(int j = 0; j < N; j++)
        if(ttable[M-1][j]) return 0;
    return 1;
}

bool solve(){
    ma = 10000;
    for(int S = 0; S < (1<<N); S++){
        memset(tans, 0, sizeof(tans));
        sum = __builtin_popcount(S);
        copy_table();
        flip_one(S);

        for(int i = 1; i < M; i++)
            for(int j = 0; j < N; j++)
                if(ttable[i-1][j]){
                    tans[i][j] = 1;
                    sum++;
                    flip(i,j);
                }
        if(ok() and sum < ma){
            ma = sum;
            for(int i = 0; i < M; i++)
                for(int j = 0; j < N; j++)
                    ans[i][j] = tans[i][j];
        }
    }
    return ma < 1000;
}

int main(){
    scanf("%d%d", &M, &N);
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            scanf("%d", &table[i][j]);
    if(solve()){
        for(int i = 0; i < M; i++)
            for(int j = 0; j < N; j++){
                printf("%d", ans[i][j]);
                if(j < N-1) printf(" ");
                else printf("\n");
            }
    }
    else printf("IMPOSSIBLE\n");
    return 0;
}

Comments