分析得知最多只可能有16次操作，而且每次操作都不相同。因此枚舉每個(gè)操作有沒(méi)有執(zhí)行即可。
以下是我的代碼：
#include<cstdio>
#include<cstring>
using namespace std;
const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
char a[5][5];
bool d[17];
int ans;
bool Black(char r[5][5])
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(r[i][j]=='w')
return false;
return true;
}
bool White(char r[5][5])
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(r[i][j]=='b')
return false;
return true;
}
void f(int i,int &x,int &y)
{
x=i/4+1;
y=i%4;
if(i%4==0)
{
x--;
y=4;
}
}
void handle(char r[5][5],int x,int y)
{
for(int i=0;i<4;i++)
{
int newx(x+dx[i]),newy(y+dy[i]);
if(newx<1 || newx>4 || newy<1 || newy>4)
continue;
if(r[newx][newy]=='b')
r[newx][newy]='w';
else
r[newx][newy]='b';
}
if(r[x][y]=='b')
r[x][y]='w';
else
r[x][y]='b';
}
void dfs(int last,int have)
{
char r[5][5];
memcpy(r,a,25*sizeof(char));
for(int i=1;i<=16;i++)
if(d[i])
{
int x,y;
f(i,x,y);
handle(r,x,y);
}
if(Black(r) || White(r))
{
if(ans>have)
ans=have;
}
for(int i=last+1;i<=16;i++)
{
d[i]=true;
dfs(i,have+1);
d[i]=false;
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
scanf("%c",&a[i][j]);
getchar();
}
ans=0x7f7f7f7f;
memset(d,false,sizeof(d));
dfs(0,0);
if(ans<0x7f7f7f7f)
printf("%d\n",ans);
else
printf("Impossible\n");
return 0;
}
posted on 2011-07-31 09:36
lee1r 閱讀(295)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：搜索