题目传送门
题意
给定一个\(4\times4\)的棋盘，棋子要么为白色要么为黑色，现在每次可以选择一个棋子，同时翻转该棋子以及与其相邻的四个棋子，要求将所有棋子都翻转成同一种颜色，问是否存在这种情况，如果存在，输出最少的翻转步数，否则输出\(Impossible\)。
思路
对于每个棋子来说，只有翻转奇数次，其颜色才会发生变化，偶数次则不会，因此我们可以将每个棋子看成只翻转\(0\)次或者\(1\)次，那么\(16\)个棋子，我们对应就有\(2^{16}\)种情况，由于不会超出时间限制，因此可以枚举每次的状态，并将枚举过的状态保存下来，同时记录最小步数即可。可以使用深度优先搜索或者广度优先搜索来做。
参考代码
广度优先搜索
//Author:Daneii
#include<iostream>
#include<queue>
using namespace std;
const int N=4;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
struct node
{
int g[N][N];
int step;
};
//用于记录状态
bool used[1<<16+1];
//判断是否满足条件了
bool check(node ns)
{
int tag=ns.g[0][0];
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(ns.g[i][j]!=tag)
{
return false;
}
}
}
return true;
}
//翻转棋子
void change(node &ns,int x,int y)
{
ns.g[x][y]=!ns.g[x][y];
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<4&&ny<4)
{
ns.g[nx][ny]=!ns.g[nx][ny];
}
}
}
//获取当前棋盘对应的状态
int getState(node a)
{
int res=0;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(a.g[i][j]==1) res+=1;
else res<<=1;
return res;
}
int main()
{
node st;
st.step=0;
//读取
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
char c;
cin>>c;
if(c=='b')
st.g[i][j]=1;
else
st.g[i][j]=0;
}
}
queue<node> qs;
qs.push(st);
while(qs.size())
{
node tmp=qs.front();
qs.pop();
if(check(tmp))
{
printf("%d\n",tmp.step);
return 0;
}
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
node ned=tmp;
change(ned,i,j);
int state=getState(ned);
if(!used[state])//如果当前状态没有出现过，我们才从此继续搜索
{
ned.step=tmp.step+1;
qs.push(ned);
used[state]=true;
}
}
}
}
cout<<"Impossible"<<endl;
return 0;
}