Algoogle

Algorithm for Programming Contest

PKU 2133 Cow Imposters

Category: PKU Tag: bfs

Cow Imposters

問題概要


目的のビット列と, E個の初期のビット列が与えられるので
初期のビット列からxorを使って生成できるビット列のうち, 目的のビット列と異なるビットの数が小さいものを求めよ.
複数ある場合は最小ステップで求まるもの, それでも定まらない場合は値が最小のものを求めよ.

解法


BFSするだけ.
ただし”生成できるビット列”を求めるので初期のビット列の扱いに気をつけること.

コード


(2133.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
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

int B, E, goal;
int bin[128];
int dist[150000];

int main(){
    scanf("%d%d", &B, &E);
    char c; scanf("%c", &c);
    for(int i = 0; i < B; i++){
        scanf("%c", &c);
        goal <<= 1;
        goal += c-'0';
    }
    scanf("%c", &c);

    for(int i = 0; i < E; i++){
        for(int j = 0; j < B; j++){
            scanf("%c", &c);
            bin[i] <<= 1;
            bin[i] += c-'0';
        }
        scanf("%c", &c);
    }
    memset(dist,-1,sizeof(dist));
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int now = que.front(); que.pop();
        if(now == goal && dist[now] >= 0) break;
        for(int i = 0; i < E; i++){
            int next = now ^ bin[i];
            if(dist[next] >= 0) continue;
            que.push(next);
            dist[next] = dist[now]+1;
        }
    }
    for(int i = 0; i < E; i++)
        dist[bin[i]] = 2 - (dist[0]==0);
    int ans, dif = 128;
    for(int i = 0; i < 1<<B; i++)
        if(dist[i] >= 0){
            int cnt = __builtin_popcount(i^goal);
            if(cnt < dif){
                ans = i;
                dif = cnt;
            }
            else if(cnt == dif && dist[i] < dist[ans]) ans = i;
        }

    printf("%d\n", dist[ans]);
    for(int i = B-1; i >= 0; i--)
        printf("%d", 1&(ans>>i));
    printf("\n");
    return 0;
}

Comments