Posted on 2011-11-25 10:43
C小加 阅读(1767)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
暴力DFS，对每一种棋子只有两种情况，翻或者不翻，而且不论是谁先翻或者谁后翻都不影响最终的结果。只有2^16种可能。剪枝：当步数小于已知的最小步数时不再搜索，当步数大于16时不再搜索。搜过之后别忘了回溯。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x7fffffff-1;
char s[4][4];
int a[5][5];
int mina=INF;
bool Achieve()
{
int t=a[0][0];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(a[i][j]!=t) return false;
return true;
}
void Flip(int i,int j)
{
a[i][j]=!a[i][j];
if(i>=1) a[i-1][j]=!a[i-1][j];
if(j>=1) a[i][j-1]=!a[i][j-1];
a[i+1][j]=!a[i+1][j];
a[i][j+1]=!a[i][j+1];
}
void DFS(int n,int pos)
{
if(Achieve())
{if(pos<mina) mina=pos;return;}
if(pos>mina) return;
if(n>16) return;
DFS(n+1,pos);
int i=n/4;
int j=n%4;
Flip(i,j);
DFS(n+1,pos+1);
Flip(i,j);
return;
}
int main()
{
memset(a,0,sizeof(a));
scanf("%s %s %s %s",s[0],s[1],s[2],s[3]);
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(s[i][j]=='b') a[i][j]=0;
else a[i][j]=1;
DFS(0,0);
if(mina<17) printf("%d\n",mina);
else printf("Impossible\n");
return 0;
}