[ACM] POJ 2133 Cow Imposters, easy DP + BFS

105 Replies

简单DP + BFS
牌子之间两两组合出新牌子， 新产生的牌子只需与原始的号码两两组合即可，即，不用考虑两个新牌子组合的情况，因为两个新牌子组合的结果必然等价与一个新牌子和原始牌子组合的结果， 否则会超时。

很自然的就可以用类似BFS里的队列来做， 我由此引发的思考是， 这种新牌子和原始牌子组合到达新point， 和BFS的思想是十分一致的， 我可以把每一个原始牌子看作一个方向， 牌子号码的每一位是一维空间。 比如 01001 这个原始牌子， 对应了一个五维空间， 这个原始牌子的方向就是 ( 0, 1, 0, 0, 1 ) 。 题目就能抽象为， 给出一个B维的空间和可以走的E个方向， 问你能到达离某个点最近的维度。

比如三维空间， 问你到达 (0,0,0) 最低的维度， 如果能到这个点本身那就是0维（0维就是一个点啦 — 我自己想的：），如果能到 (0,0,1) 就是最少1维， 能到 (0,1,1) 是最少二维。 有人问那 (0,0,0) 到 (0,1,1) 不是也能直接连线么， 这样想的话我们要考虑我们只能走给出的原始牌子对应的方向，我们甚至不是顺着xyz轴平移的，而是XOR运算的移动 ^^，所以从 (0,0,0) 到 (0,1,1) 必须顺着两个方向移动， 拉出一个二维空间。 相应的 (0,0,0) 到 (1,1,1) 就要穿越三维空间了。

在B>3的情况下就需要像我一样具有多维的想象力才能理解:)

细节：
变量名写明朗不会死斯基， 把B和E搞混了搞了好久
我输出的时候试图把2进制的每位乘上10来直接放在int里输出，但是没考虑到虽然它实际上是2^16的数，这样转换一下就变成10^16， 不止int的范围了

代码：
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;

int inputBin(int B) {
while (getchar() != ‘\n’)
;
int temp = 0;
for (int i = B – 1; i >= 0; i–)
temp += (getchar() – ‘0’) << i;
return temp;
}

int main() {
int B, E;
int map[1 << 16];
int que[1 << 16];
int GOAL;

scanf("%d%d", &B, &E);
GOAL = inputBin(B);

//Initialize
for (int i = 0; i < 1 << B; i++)
map[i] = -1;

for (int i = 0; i < E; i++) {
int temp = inputBin(B);
map[temp] = 0;
que[i] = temp;
}

//BFS
int p0 = 0;
int p1 = E – 1;

while (p0 <= p1) {
if (que[p0] == GOAL)
break;

int temp = que[p0];
for (int i = 0; i < E; i++) {
int created = temp ^ que[i];
if (map[created] != -1)
continue;
//if(created==26)
//printf("**\n");
map[created] = map[temp] + 1;
que[++p1] = created;
}
p0++;
}

//DetailFucker: Strip needs to be "created" as the text described.
int bla = map[0] == 0 ? 1 : 2;
for (int i = 0; i < E; i++)
map[que[i]] = bla;
map[0] = 1;

int result[17];
int resultA[17];
memset(result, 0xff, sizeof(result));
for (int i = 0; i <= p1; i++) {
int diff = 0;
int temp = que[i];
for (int k = 0; k < B; k++)
diff += ((temp >> k) & 1) ^ ((GOAL >> k) & 1);
if (result[diff] == -1 || result[diff] > map[temp] || (result[diff]
== map[temp] && resultA[diff] > temp)) {
result[diff] = map[temp];
resultA[diff] = temp;
}
}

int resultN;
for (resultN = 0;; resultN++) {
if (resultN > B)
exit(1);
if (result[resultN] != -1)
break;
}

printf("%d\n", result[resultN]);
int notYet = resultA[resultN];
for (int i = B – 1; i >= 0; i–)
printf("%d", (notYet >> i) & 1);
printf("\n");

return 0;
}
[/cpp]

105 thoughts on “[ACM] POJ 2133 Cow Imposters, easy DP + BFS”

Leave a Reply

Your email address will not be published. Required fields are marked *