Posted on 2011-11-25 10:43
C小加 閱讀(1787)
評論(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;
}