Posted on 2011-11-25 10:43
C小加 閱讀(1787)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告
暴力DFS，對(duì)每一種棋子只有兩種情況，翻或者不翻，而且不論是誰(shuí)先翻或者誰(shuí)后翻都不影響最終的結(jié)果。只有2^16種可能。剪枝：當(dāng)步數(shù)小于已知的最小步數(shù)時(shí)不再搜索，當(dāng)步數(shù)大于16時(shí)不再搜索。搜過(guò)之后別忘了回溯。
#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;
}