POJ-1753 解题报告

题意简述

4*4的格子放有黑白两面的棋子16个,翻转任一棋子会使其上下左右棋子一同翻转。给定初始状态,求达到所有棋子全黑或全白的最少翻转次数。如果无解,输出Impossible。

POJ1753附图
POJ1753附图

算法分析

首先容易证明:

1、翻转棋盘上任意个棋子,棋盘达到的状态与各棋子被翻转的先后顺序无关。

2、对每个棋子进行2次及以上的翻转没有意义。∵ 偶数次翻转结果与不翻转相同,奇数次翻转结果与翻转1次相同。

于是问题被简化为:棋盘上部分棋子经过1次翻转,能使棋盘达到全黑或全白状态。求所需翻转棋子的最少数目。

因为一共只有16个棋子,故只有2^16种可能。

——————————————————————分割线——————————————————————

具体算法:

DFS。

输入时将数据转化为1维01数组。

dfs(array,position,step,answer)四个形参,array传递数组,position传递当前位置,step传递深度(也即翻转个数),ans传递当前最优答案。

深搜时先判断当前状态是否满足条件,满足则和当前答案对比,若更优则替换。返回。

若深度超出16也返回。

改变当前位置,以及上下左右共5个点状态。

dfs(array,position+1,step+1,answer)。

回溯。只需再次改变5个点状态即可。

dfs(array,position+1,step,answer)。

Problem Status: AC。时间94ms,内存360k

——————————————————————分割线——————————————————————

TIPS:

WA了好几次。有几个小细节要注意:

1、翻转时,如果遇到行末则不翻转下一个,遇到行首则不翻转上一个。可以通过mod 4的值来判断。

2、DFS时,需先判断是否满足条件(全黑或全白)再判断位置是否越界(position<16)。因为有可能所有棋子都需要翻转,由于判断本次翻转是否成功是在下一层递归中,所以即使position越界也需先验证一次上次翻转后是否达到所需状态。

——————————————————————分割线——————————————————————

优化:

1、一维01数组可以使用一个int类型变量替代。2个字节16位就可以表示了。翻转操作采用位运算实现。(这个还没试过,据说时间达到16ms,以后有机会试下。)

2、网上的解题报告说据说有一种枚举可以达到时间0ms?还没找到具体算法。要去膜拜下。

程序样例

[c]
#include&lt;stdio.h&gt;

void change(int s[],int pos)
{
if (s[pos]==0) s[pos]=1; else s[pos]=0;
if ((pos+1&lt;16)&&(pos%4!=3))
if (s[pos+1]==0) s[pos+1]=1; else s[pos+1]=0;
if ((pos-1&gt;=0)&&(pos%4!=0))
if (s[pos-1]==0) s[pos-1]=1; else s[pos-1]=0;
if (pos+4&lt;16)
if (s[pos+4]==0) s[pos+4]=1; else s[pos+4]=0;
if (pos-4&gt;=0)
if (s[pos-4]==0) s[pos-4]=1; else s[pos-4]=0;
}

int finish(int s[])
{
int i;
for(i=1;i&lt;16;i++)
if (s[i]!=s[0]) return 0;
return 1;
}

void try(int s[], int pos, int step, int *ans)
{
if (finish(s))
{
if (step&lt;*ans) *ans=step;
return;
}
if (pos&gt;15) return;
change(s,pos);
try(s,pos+1,step+1,ans);
change(s,pos);
try(s,pos+1,step,ans);
}

int main()
{
int s[16];
int i,j,ans=17;
char t[5];
for(i=0;i&lt;4;i++)
{
scanf("%s",t);
for(j=0;j&lt;4;j++)
if (t[j]==’b’) s[i*4+j]=1;
else s[i*4+j]=0;
}
try(s,0,0,&ans);
if (ans==17) printf("Impossible"); else printf("%d",ans);
system("pause");
return 0;
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *