讨论 / 广搜,全部可能都考虑,附加代码,希望对你有帮助
15873562302 2016-03-22 02:36:03
点我顶贴 收藏 删除
#include <stdio.h>

#include <cstring>

#include <iostream>

using namespace std;

char a[5][5];

int sum,fx[4][2]={{0,1},{1,0},{-1,0},{0,-1}},head,tail,f;

struct add

{

int cs,b[20];

}q[100000];

int check()

{

int i,j;

for(i=0;i<4;i++)

for(j=0;j<4;j++)

{

if(a[0][0]==a[i][j])

{

continue;

}

else

{

return 0;

}

}

return 1;

}

void fz(int l,int w)

{

int x,y,i;

x=l;

y=w;

if(a[l][w]=='b')

{

a[l][w]='w';

}

else

{

a[l][w]='b';

}

for(i=0;i<4;i++)

{

l=x+fx[i][0];

w=y+fx[i][1];

if(l>3||w>3||l<0||w<0)

continue;

if(a[l][w]=='b')

{

a[l][w]='w';

}

else

{

a[l][w]='b';

}

}

}

void bfs()

{

while(1)

{

if(tail>70000)

break;

for(int k=q[head].b[q[head].cs]+1;k<16;k++)

{

f=0;

q[tail].cs=q[head].cs+1;

for(int j=1;j<=q[head].cs;j++)

q[tail].b[j]=q[head].b[j];

q[tail].b[q[tail].cs]=k;

for(int i=1;i<=q[tail].cs;i++)

{

fz(q[tail].b[i]/4,q[tail].b[i]%4);

}

if(check())

{

f=1;

break;

}

for(int i=q[tail].cs;i>=1;i--)

{

fz(q[tail].b[i]/4,q[tail].b[i]%4);

}

tail++;

}

if(f)

break;

head++;

}

return;

}

int main()

{

int i,j,k;

for(i=0;i<4;i++)

scanf("%s",a[i]);

k=0;sum=10000;

while(k!=16)

{

fz(k/4,k%4);

if(check())

{

sum=1;

break;

}

fz(k/4,k%4);

q[k].cs=1;

q[k].b[q[k].cs]=k;

k++;

}

head=0;

tail=16;

if(!check()&&sum==10000)

{

bfs();

if(f)

{

printf("%d\n",q[tail].cs);

}

else

{

printf("impossible\n");

}

}

else

{

if(sum==10000)

sum=0;

else

;

printf("%d\n",sum);

}

}

查看更多回复
提交回复