http://poj.org/problem?id=1753

搜索什么的一直都没入门。。。于是找来经典题目练习,于是果断不会,于是经过看题解什么的用了大半天的时间总算对这道题搞明白一些。当然对dfs的思想也有进一步的理解。

题意很好懂,目的即是要看在多少步可将棋子翻转成全一色。第一个要解决的问题:如何判断结束条件。这个地方想了很久,大概能想的差不多了http://www.189works.com/article-58021-1.html,这个地方的解释比较全面,我也就不掺和了(当我没想明白,这里用抽屉原理怎么想?)。解决了第一个问题,基本能下手写一些了。剩下的问题在注释里表明。贴代码(虽然基本上是把现成的抄了遍。。。)

除了dfs好像更多人用到了枚举和位运算,bfs也可以实现,还得在加深研究

 

#include”stdio.h”
int map[6][6];
int step,flag=0;
int dir[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};

int judge()
{
int i,j;
for(i=1;i<5;i++)
{
for(j=1;j<5;j++)
{
if(map[i][j]!=map[1][1])
return 0;
}
}
return 1;
}//判断是否成立

void roll(int y,int x)
{
int i;
for(i=0;i<=4;i++)
map[y+dir[i][1]][x+dir[i][0]]=(map[y+dir[i][1]][x+dir[i][0]]==1)?0:1;
}//翻转

//接下来是重头戏

int dfs(int y,int x,int deep)//deep为当前翻转了的个数
{
if(deep==step)//与当前判断的步数想通了,即要进行判断
{
flag=judge();
return 0;
}
else if(y==5||flag)//如果判断到了第五行那也就是说,前四行都满足条件了。
return 1;
roll(y,x);//当前位置翻转
if(x<4)//若等于四,则下一个搜索的对象为下一行的第一个
dfs(y,x+1,deep+1);
else
dfs(y+1,1,deep+1);
roll(y,x);//之前的假设不成功,进行到了这步的话就要把翻过去的那枚棋子再翻回来
if(x<4)
dfs(y,x+1,deep);//这个地方是我理解了很长时间的,这里是deep,而不是deep+1,。因为进行到此说明之前的那个翻转不是正解,又回到原状态。所以进行到此就说明,这是本次搜索要翻转的首个
else
dfs(y+1,1,deep);
return 0;
}

int main(){
int i,j;
char c;
for(i=1;i<5;i++)
{
for(j=1;j<5;j++)
{
scanf(“%c”,&c);
if(c==’b’)
map[i][j]=1;
else
map[i][j]=0;
}
getchar();//这个地方也要注意,否则会把’\n’读进来
}
for(step=0;step<=16;step++)//列举翻转0–16枚的情况(解释即上边的网址)
{
dfs(1,1,0);
if(flag==1)
break;
}
if(flag==1)
printf(“%d\n”,step);
else
printf(“Impossible\n”);
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation