[转帖]ACM竞赛试题分析

ilikenba 发表于 2005-2-17 10:54

<XML></XML>

<TABLE height="100%" cellSpacing=0 cellPadding=0 width="100%" border=0>

<TR>
<TD width=74><IMG src="http://www.frontfree.net/articles/pages/0000000688/title.gif" border=1></TD>
<TD vAlign=top width="100%">
<TABLE height="100%" cellSpacing=0 cellPadding=0 width="100%" border=0>

<TR>
<TD class=artitle vAlign=top colSpan=2>ACM竞赛试题分析</TD></TR>
<TR vAlign=top>
<TD align=left>原创：怒火之袍</TD>
<TD class=text vAlign=top align=right>2002年12月1日 </TD></TR></TABLE></TD></TR>
<TR>
<TD class=arcontent colSpan=3>
上一次笔者简单地介绍了ACM/ICPC程序设计竞赛的基本信息和发展状况，这次则试着向大家展示一下其中一个比较简单的题目，并作出一些粗浅的分析，希望能以此让大家有个更感性的认识。
从“蛇和梯子”的问题谈对信息的过滤处理
2002年11月2日阿拉伯和北非地区第5届地区赛题目G 蛇和梯子
问题简述：“蛇和梯子”是一个在N*N（0<N<=20)的方格棋盘上进行的游戏。（见下图）
<IMG src="http://www.frontfree.net/articles/pages/0000000688/pic001.jpg" border=0>
方格从1到N的平方编号。除了1号和最后1号方格，其他的格子有可能有蛇或梯子存在（蛇和梯子的数量及具体位置由输入确定，它们的数量都在100之内并且蛇和梯子不能临近放置，也就是在任何了放置两者首尾的方格之间至少还有一个未放置任何东西的格子）。开始的时候玩家把他们的标志物放在1号格子中。玩家轮流以扔骰子的方式移动他们的指示物。如果一个指示物到达了一条蛇的嘴部，则把它移回蛇的尾部。如果一个指示物到达了一个梯子的底部则将它移动到梯子的顶部。如果你是一个可以自由控制骰子的高手，现在请求出你至少需要扔几次骰子才能到达标为N^2的格子。（比如在上图所示例一中，你的方案应该是走4步到达5并由梯子上升到16，再走4步到达20并由梯子上升到33，然后走3步。这样，你一共需要扔3次骰子。而在例二中，你的方案应该是连扔4个6。）
比较容易看出，这个问题是不能用贪心算法解决的，因为你不能保证在这步到达一个数码比较大的格子就意味着最好的效率（即使是通过梯子到达了一个这步所能到达的最大号码的格子），也就是说，号码的大小并不能代表从这个格子到达终点所需要的步数上的多少，这就带给我们一个启发：蛇和梯子真的需要看成是两个东西来分别处理么？实际上确实是不需要的，蛇和梯子的本质就是我们经常在游戏中说的“单向传送点”，只不过梯子的底部是入口而顶部是出口，蛇的嘴部是入口而尾部是出口罢了，对于他们的描述完全可以选择相同的结构：
struct SnakeAndLadder
{
 int from,to;
};
接下来要考虑的是解决问题的方法。贪心算法被否定之后，我们的选择可能会是搜索，对于本题所采用的搜索显然应该以广度优先的方式进行，但是稍加分析我们就会发现如果单纯地采用广度优先搜索会产生许多重复的结点，现在我们将指示物处于某格的结点简称为结点X，那么比如在例1中，第1步过后，队列中存放的结点是2，23，4，16，6，7，在第二步时，当结点2成为扩展结点时将生成结点23、4、16、6、7、8，其中只有8不存在于当前活结点队列中，即使加以判断，不把重复的结点再次加入队列中，那至少也需要对活结点队列进行搜索。实际上我们完全有更好的方法。
应该意识到，采用树状结构和搜索的方法处理问题其重要的一点是利用祖先结点的差异性来对儿子结点做不同的处理。然而在本题中，儿子结点的生成只依赖于父结点的信息而与其它祖先结点无关，所以采用树来描述这个过程其实是多余的。在走了若干步之后，对于一个特定的格子实际上只有两种状态的区分：
1、在走了这些步数之后存在一种方案使指示物位于此格中；
2、不存在这样的一种方案。
所以我们可以用一个N^2大小的数组来描述若干步之后可以到达的格子的集合，其中每一个元素描述一个格子的状态，0表示不存在一种方案到达，1表示存在至少一种方案到达。这样，我们从表示第n步状态的数组，完全可以推出表示第n+1步状态的数组，而且在第n+1步状态的数组得到之后，表示第n步状态的数组也就不再存在利用价值了。一旦数组中表示最后一个格子的元素成为1，就表示可以通过这个步数完成任务了。
比如在例1中，描述棋盘状态的数组其变化过程应该是：
<TABLE width="100%" bgColor=#000000 border=0>

<TR>
<TD width="35%" bgColor=#666666>
<DIV class=unnamed1 align=center>描述状态</DIV></TD>
<TD width="65%" bgColor=#666666>
<DIV align=center>
数组元素的内容（从表示第1个格的元素排列到表示最后一个格的元素）</DIV></TD></TR>
<TR>
<TD class=unnamed1 width="35%" bgColor=#ffffff>起始状态</TD>
<TD class=unnamed1 width="65%" bgColor=#ffffff>100000000000000000000000000000000000</TD></TR>
<TR>
<TD class=unnamed1 width="35%" bgColor=#e0e0e0>第1步之后</TD>
<TD class=unnamed1 width="65%" bgColor=#e0e0e0>010101100000000100000010000000000000</TD></TR>
<TR>
<TD class=unnamed1 width="35%" bgColor=#ffffff>第2步之后</TD>
<TD class=unnamed1 width="65%" bgColor=#ffffff>000101111111100111101111111110001000</TD></TR>
<TR>
<TD class=unnamed1 width="35%" bgColor=#e0e0e0>第3步之后</TD>
<TD class=unnamed1 width="65%" bgColor=#e0e0e0>000001111111111111101111111111111101</TD></TR></TABLE>
到第3步之后，数组的最后一个元素已经变为了1，这即表明存在一种方案，使得我们扔3次骰子就可以完成任务。以下是实现此算法的主要部分代码，数组下标0——size*size-1的元素分别表示了从第1格到最后一格的状态，step记录步数，obstacle是struct SnakeAndLadder的向量，描述了蛇和梯子的传送入口和出口：
<TABLE cellSpacing=0 cellPadding=0 width="100%" bgColor=#e0e0e0 border=0>

<TR>
<TD>
//初始化状态数组和步数记录
for (j=1;j<size*size;j++)
grid=0;
grid=1;
step=0;

while (grid==0)
{
 for (j=0;j<size*size;j++)
 gridbak=grid;
for (j=0;j<size*size;j++)
 grid=0;
for (j=0;j<size*size-1;j++)//搜索所有的格子（最后一格不用搜索因为在过程结束前它一定为0）
{
 if (gridbak==0)//若在上一步无法到达此格则跳出
 continue;
 for (k=1;k<=6;k++)
 {
 test=0;
 if (j+k>size*size-1)
 break;
 for (l=0;l<obstacle.size();l++)//如果此格是一个传送入口，将传送出口的格子可达
 {
 if (obstacle.from==j+k)
 {
 grid.to]=1;
 test=1;
 break;
 }
 }
 if (test==0 && grid==0)
 grid=1;
 }
}
step++;//步数加一
}
</TD></TR></TABLE>
过程执行完毕后，输出step即可。

另外，笔者认为此题规定棋盘为N*N大小只是为了输入方便，举例画图方便，实际上多大的棋盘都是一样可以看作一条直线，数组也是用一维的便足够了。
通过对这道题的分析，笔者想说的是，ACM竞赛试题其实有一些并没有多大的绝对难度，但是它通过一些附加的信息来制造干扰和人为复杂化，这样，一些没有经验和实力不足的选手在有限的时间内对题目的解决思路和总体难度分析都要产生偏差，可实力雄厚的人则能一眼看透问题的实质所在并以最简洁的算法实现，这是通过大量练习才能取得的。并不是所有的算法爱好者都一定要通过参加竞赛来提高，但是竞赛中的一些问题确实向我们展示了一些值得注意、思考和总结的方法，希望大家都能充分利用这些资源取得属于自己的进步。</TD></TR></TABLE>
[此贴子已经被作者于2005-4-22 17:22:10编辑过]

whutes 发表于 2005-4-2 12:09

回复：（ilikenba）[转帖]ACM竞赛试题分析

Yeah, some posts are pasted at wrong places.

happy_cser 发表于 2005-4-22 15:58

不知道是怎么回事运行代码也不行啊晕

ilikenba 发表于 2005-4-22 17:22

得到楼上的建议!我将它修复好了!谢谢!

codingCTM 发表于 2006-12-4 21:34

回复：（ilikenba）[转帖]ACM竞赛试题分析

顶一下

zhaoyunfei1126 发表于 2007-4-7 11:22

顶一下！！！！

Jackge 发表于 2011-11-20 22:12

我也顶一下……

cmd2.com电影 发表于 2011-11-30 03:38

我也来了，哈,看一看

发表于 1970-1-1 08:00

页: [1]

数学建模社区-数学中国's Archiver