在POJ上提交用的是枚举,刚学了bfs
各种混乱,WA了
# include <stdio.h>
# include <string.h>
# define MAX 65536
# define INDEX(i) ((i)>>3)
# define OFFSET(i) ((i)%8)
# define GET_BIT(i) (vis[INDEX(i)]>>OFFSET(i) & 0x1)
# define SET_BIT(i) (vis[INDEX(i)] |= 0X1<<OFFSET(i))
char vis[INDEX(MAX)+1];
unsigned short Q[MAX+20];
unsigned short f[] = {0x13,0x27,0x4e,0x8c,0x131,0x272,0x4e4,0x8c8,
0x1310,0x2720,0x4e40,0x8c80,0x3100,0x7200,0xe400,0xc800
};
int flip(unsigned short start, unsigned short x)
{
int i;
for (i = 0; i < 16; ++i)
if ((x>>i) & 0x1) start ^= f[i];
if (0==start || 0xff==start) return 1;
return 0;
}
int bfs(unsigned short start)
{
unsigned short x;
int i, front, rear;
front = 0;
rear = 1;
SET_BIT(0);
while (rear!=front)
{
x = Q[front++];
//printf("front = %d, rear = %d, 0x%x\n", front, rear, x);
if (flip(start, x)) return x;
else for (i = 0; i < 16; ++i)
if ((x>>i) & 0x1) continue;
else if(!GET_BIT(x+(0x1<<i)))
{Q[rear++] = x+(0x1<<i);
SET_BIT(x+(0x1<<i));
}
}
return -1;
}
int main()
{
unsigned short start, i;
int chg, ans;
char ch;
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
start = i = 0;
while (i < 16)
{
ch = getchar();
if (ch == 'b')
{
start += 0x1<<i;
//printf("1");
++i;
}
else if (ch == 'w')
{
++i;
//printf("0");
}
}
//printf("\n");
ans = 0;
chg = bfs(start);
if (chg == -1) printf("Impossible\n");
else
{
for (i = 0; i < 16; ++i)
if (chg>>i & 0x1) ++ans;
printf("%d\n", ans);
}
return 0;
}