【题目大意】
有一个4x4规格的一个棋盘，现在有16个一面黑一面白的棋子分布在这个棋盘上。
翻转一个棋子能够使它以及它上下左右的四个棋子从黑变白，从白变黑。
现在问你至少要经过多少次操作才能够使得整个棋盘的颜色相同。
【分析】
考虑到是4x4的规模，想到用BFS枚举+判重。
注意题目的内存限制是64MB，如果普通的用一个二维数组记录状态可能会超过内存限制。
考虑位运算，下面给出AC代码。
#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
const int INF=0x7fffffff;
using namespace std;
struct map
{
int shu[];//位运算按行存储
int times;//翻转次数
map(){memset(shu,,sizeof(shu));}
}data;
bool hash[(<<)+];//哈希表 bool test(map t);//检测
map change(map t,int x,int y);
void print();//检测函数
int bfs();//广搜
int h(map t);//哈希函数 int main()
{
int i,j;
//文件操作
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
memset(data.shu,,sizeof(data.shu)); //读入数据
for (i=;i<=;i++)
{
if (i!=) getchar(); //读取换行符
for (j=;j<=;j++)
{
char temp;
scanf("%c",&temp);
//注意这里存储是从左向右存储
if (temp=='w') data.shu[i]=(data.shu[i]<<)+;
else data.shu[i]=(data.shu[i]<<)+;
}
}
int ans=bfs();
if (ans==INF) printf("Impossible\n");
else printf("%d",ans);
return ;
}
bool test(map t)//检测函数
{
int cnt=,i,j;
for (i=;i<=;i++) cnt+=t.shu[i];
if (cnt== || cnt==(*)) return ;
return ;
}
int bfs()
{
queue<map>Q;
memset(hash,,sizeof(hash));
int i,j;
data.times=;
hash[h(data)]=;
Q.push(data);//加入队列
while (!Q.empty())
{
map u=Q.front();Q.pop();
if (test(u)) return u.times;
for (i=;i<=;i++)
for (j=;j<=;j++)
{
map v=u;
v=change(v,i,j);
v.times=u.times+;
if (test(v)) return v.times;
if (hash[h(v)]==) continue;//哈希判重
Q.push(v);
hash[h(v)]=;
}
}
return INF;
}
int h(map t)//哈希函数
{
int temp=,i,j;
for (i=;i<=;i++) temp=(temp<<)+t.shu[i];
return temp;
}
//第x行，第y个
map change(map t,int x,int y)
{
t.shu[x]=((t.shu[x])^(<<(-y)));//本身
t.shu[x+]=((t.shu[x+])^(<<(-y)));//上面
t.shu[x-]=((t.shu[x-])^(<<(-y)));//下面
if (y!=) t.shu[x]=((t.shu[x])^(<<((-y)+)));//左边
if (y!=) t.shu[x]=((t.shu[x])^(<<((-y)-)));//右边
return t;
}