1753 Flip Game

和咱天的HDU 1882 Strange Billboard 差不多

不过这题的数据量要小一些,4*4的规模,用二进制表示完全可以用INT型存

http://acm.pku.edu.cn/JudgeOnline/problem?id=1753

#include <iostream>

#include <cstring>

using namespace std;

char g[4][4];

int counter;

int temp1,temp2;

int start;

int find(int x);

int d[4] =

{

0xf000,

0x0f00,

0x00f0,

0x000f

};

int main()

{

int i,j,k,m,n,t;

while (scanf("%s",g[0])!=EOF)

{

start = 0; //记录开始的状态

for (i=0;i<4;i++) //转换前四位15~12

{

if (g[0][i] == 'b') // 如果是黑色的

{

start = start | (1<<(15-i));

}

}

k = 11;

for (i=1;i<=3;i++) //输入及转换后12位:11~0

{

scanf("%s",g[i]);

}

for (i=1;i<=3;i++) //输入及转换后12位:11~0

{

for (j=0;j<4;j++)

{

if (g[i][j] == 'b') // 如果是黑色的

{

start = start | (1<<(k));

}

k--;

}

}

// printf("%d/n",start);

//输入及转换完成-----------------------------------

int mincount=-1;

for (i=0;i<16;i++)

{

//printf("%d/n",counter);

//i+((1<<12)-1)

if (find(i)) //如果可以达到目标态

{

if ((counter < mincount) || (mincount == -1))

{

mincount = counter;

}

}

}

if (mincount == -1) //如果一直不可达

{

//那么

printf("Impossible/n");

}

else

{

printf("%d/n",mincount);

}

}

return 0;

}

int find (int x) //参数传第一行的转换方法

{

int i,j,change1 = 0,change2 = 0,counter1 = 0,counter2 = 0;

temp1 = start;

temp2 = ~start;

for (i=0;i<4;i++) //change each line

{

if (i == 0) //第一行的转换

{

change1 = (x<<12);

change2 = (x<<12);

}

else

{

change1 = temp1&(d[i-1]);//上一行的位情况

change2 = temp2&(d[i-1]);

temp1 = temp1 & (~d[i-1]);

temp2 = temp2 & (~d[i-1]);

}

//然后开使转化

if (i)

{

temp1 ^= change1>>4;

temp1 ^= (change1>>(4+1))&d[i];

temp1 ^= (change1>>(4-1))&d[i];

temp1 ^= (change1>>(4+4))&d[i+1];

temp2 ^= change2>>4;

temp2 ^= (change2>>(4+1))&d[i];

temp2 ^= (change2>>(4-1))&d[i];

temp2 ^= (change2>>(4+4))&d[i+1];

}

else

{

temp1 ^= change1;

temp1 ^= (change1>>1)&d[i];

temp1 ^= (change1<<1)&d[i];

temp1 ^= (change1>>4)&d[i+1];

temp2 ^= change2;

temp2 ^= (change2>>1)&d[i];

temp2 ^= (change2<<1)&d[i];

temp2 ^= (change2>>4)&d[i+1];

}

//计算counter of change

for (j=0;j<16;j++)

{

if ((change1>>j)&1)

{

counter1++;

}

if ((change2>>j)&1)

{

counter2++;

}

}

}

if (temp1 && temp2 != 0xffff)

{

return 0;

}

else

{

if (!(temp1 && temp2 != 0xffff))

{

counter = counter1<counter2?counter1:counter2;

}

else if (!temp1)

{

counter = counter1;

}

else

counter = counter2;

return 1;

}

}

/*

test data:

wbbw

wwbw

wbbw

wbbb

bwwb

bbwb

bwwb

bwww

bbbb

bbbb

bbbb

bbbb

wwww

wwww

wwww

wwww

*/