现在的位置: 首页 > 综合 > 正文

Google Code Jam 2009 资格赛题目B 分析

2013年11月14日 ⁄ 综合 ⁄ 共 2384字 ⁄ 字号 评论关闭

这个问题的解答拖了好久,终于有时间弄出来了。这篇先说参考的思路,下一篇再上代码。

 

参考比赛选手的可下载程序清单,整理思路。学习人家是如何把实际问题转换为代码,以及其中的编程技巧的。
关于分水岭问题,阅读了两个人的程序清单,发现在程序大体框架上很相似,在具体实现过程中略有不同。
关于搜索最低海拔的方向优先级问题:优先级是[上,左,右,下]。
对于数组,我们则是按照这个优先级顺序来比较该数组元素的四个方向上的相邻元素的值的大小关系。
           |[-1][ 0]|                     |上|
[ 0][-1]|[ 0][ 0]|[ 0][ 1] -->  左|中|右
           |[ 1][ 0]|                     |下|
因此,对于这个方向的表述,在两个程序中略有不同,反映了两种方式,一种是xy结合在一起的,一种是xy分开的。
direction[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
directionx[4] = {-1, 0, 0, 1};
directiony[4] = {0, -1, 1, 0};
这个方向的问题,是在需要搜索算法的时候用到的。
而这个算法也是程序中最为重点的地方。
其他的部分,两个程序的实现比较一样。我仅认真分析了其中的一个程序,因此仅将该程序的思路表述一下。
main函数开始
|   open 2文件 一个read 一个write,因为read infile是读取数据,write outfile是输出最后结果。
|   首先读取infile的第一行TotalCases,这个整数表示了infile中含有多少个case。
|   然后for TotalCases次循环,即有多少个数据case需要处理就循环多少次。
|
|   然后读取一行 n m ,现在我们在整个大的循环体内部,每一次循环我们都面对一个case。
|   这个n m表明了每一个case的行列是多少,也就是每一个case的大小。
|   用双重循环for n for m来读取case中的每一个元素,放到a[100][100]数组里。所以这个数组a就是存放case原始数据的数组。
|
|   数据读出来了,那么下面就应该对case进行搜索了,我们是把搜索和标记过程分开处理的。
|  
|   for n for m 遍历数组元素
|   |
|   |   对于数组中每一个元素的处理,我们将要按照方向优先级搜索其上左右下四个方向的相邻元素,  
|   |   看看它们的大小,因此我们需要一个变量k来进行4次方向循环,每次循环通过当前xy加上direction的xy就可以得到周围四个方向的
|   |   数组访问下标tx,ty。用什么表示到无所谓了。
|   |   对于数组边界值的搜索涉及到一个边界判断的问题,即不能访问不合法的地址的数据。
|   |   另外,为了提取出这个最小的值,它可能是元素本身,此时该元素实际上就已经是水池了;
|   |   也有可能是元素周围的值更小,则待会这就是流动的方向。为了提取它我们需要一个变量来保存这个最小值,
|   |   用min来始终等于这个最小值。
|   |   这里还涉及到了一个方向记录的问题,即每个元素实际上具有一个属性,是记录它的流动方向的,流向哪里和从哪里流过来的。
|   |   程序中用到了一个g[][][4]来表示,给我的感觉是4层……,我尝试用结构体来表示该属性。
|   |   还有一个问题就是要记录当前访问的数组元素和它的方向上最小的元素的属性,都要修改。这里用到了一个技巧
|   |   我们看 上左右下 对应着 0 1 2 3 然后想想逻辑,假设当前元素为x,它的四个方向上最小的元素是y
|   |   则我们可以假设 x的左边就是y的右边 x的上面就是y的下面,上下左右都是这个道理,而上和下,左和右是互补的,和都是3,
|   |   也就是说,0=3-0 1=3-2,因此用g[][][dir]和g[][][3-dir]这个下标是可以完成这个任务的。
|   |
|   /_  这样,在这一次的遍历之后,g[][][]的数组里面就保存了每个元素的方向属性。我们对每个元素的周围的搜索范围都是1个格。
|  
|   为了最后标记case,还需要一个数组,用来做标记 flag[][]。
|
|   for n for m 遍历数组
|   |
|   |   判断当前元素的flag标记是否被置位,
|   |   如果置位了,说明当前点已经被流域流过了,
|   |   如果没有被置位,则说明当前点尚未开发,
|   |   根据规则,标记是从a开始的,因此有一个变量p++用来做'a'=p;p++可以得到a b c d ...标记。
|   |   在这里,两个程序都用到了递归的方法来进行路径的判断。
|   |   应该说我学过递归,但是不知道在这里可以用递归……,这就是差距啊。好好学习了。
|   /_  递归函数在后面给出。
|  
|   经过这一轮遍历之后,该标记的都已经标记上了,剩下的就是输出结果了。  

|   for n for m 遍历数组
|   |
|   /_  打印出结果
|
/_ main函数结束

recursion函数 递归函数 该函数的主要作用是对元素的标记属性进行置位,并且按照步长为1格进行方向优先级搜索
|                      说白了就是,该元素和该元素四个方向上的元素,置位标记属性。
|
/_  两个程序中一个传入了x y c,一个传入了x y 对于c 在输出时进行处理。我认为第一种方法更清晰些。

一开始我在思考这个题目的时候,觉得既然要进行路径的搜索,那么得用到链表之类的比较高级的方式吧。
看了人家的程序,人家用for循环和递归就搞定了,说明在算法上我还不行啊。
这个方法王君同学也提出来了,感觉十分类似,但是当时没有想到用递归可以做到。
调试了几个小时,用C语言的方法实现了,但是程序长度是人家用CPP实现的两倍。没有用那么多数组,用了结构体来实现的。 

抱歉!评论已关闭.