信息学集训队作业center

1、IOI2003中国国家集训队难活有一个大厅最近要召开一个很重要IOI2003中国国家集训队难活有一个大厅最近要召开一个很重要的会议，因此会议的组织者请了一个清洁公司来给大厅机来完成清洁工作。机器是一个边长为L形(2L=100)覆感【正文算法动以后至少能够清扫面积为1 的方格，下同）时，选择可清感【正文算法动以后至少能够清扫面积为1 的方格，下同）时，选择可清扫的面积最大的进行移动。如图1，黑色方表积为2的方格，向右可以清扫面积为3的方格，按照这种算法，此时向右移动BA当机器走到一个方格A以后，周围没有任何区域可以移动，递归就进行回溯，找到一个可以向周围移动的方格B。然后用宽度优先搜索找A到B的

2、路径，途中0的区域。如图2，箭头代表利用BFS 找出的路径。从A 走到B 以后，还是利用刚才的策略继续寻找。但是，如果出现一个狭长通道有许多小分支的情况，在H较小的情况下，这种策略就可以产生比较差的答 针对这种缺点，可以设计一个对策：在读入数据以后，先用BFS找出起点到所有能达到的方格的最短距离dist(rc)，并求出(rc)所在的最大矩形空地area(rc)。然后，找出一个dist(r,carea(r,c)最大的点M。在未达到M的时候，所有的移动都以能否更靠近M为评判的第一标准。达到M以后XX23利用这种方法，能够在许多情况下都取得比较好的效果。不过，需要注意的是，4 个方向的优先级有级关系

3、，否则利用这种方法，能够在许多情况下都取得比较好的效果。不过，需要注意的是，4 个方向的优先级有级关系，否则程序得出的解不一定能令人满意。由此，我猜想，是否能有办法，根据当时的情况，动态 算法对于一个非常空旷的地图，算法1虽然能够获得较优的解，但并不很令人满意。针对这种地图，我设计了算法2。但是有的时候这种方法其实效果很差，因为它可能会导致机器“陷入泥潭而不能自拔如图4，机器A，就无路可走了，接下来只能原地打转，很浪费。因此，可以再追加一个规定：机器一旦无路可走，就使用BFS 找到最近的一个未清扫的方格B，从A 移动到B 继续清扫。数据C BEFA 向A进发。如果走C、D分支中的任意一个，回头

4、的时候都会造成巨大浪费。如果走E、F，浪费则会相对B 代价最少的覆盖方案，因此最后仅将主干通道和B 的全部以及A BA算法2的方案，覆盖了B、C、D的全部，以及主干通道和E的一算法2的方案，覆盖了B、C、D的全部，以及主干通道和E的一部分。虽然在C、D通道浪费了不少移动，但最后的面积却是33737。这再次说明，算法1所得出的方案，虽然目标完全正确，但是在遍历的数据（图太大，不好截，估计是出题者利用Test_creator随便画出来的，是一个很开阔、很空旷的地图L也很大，L=35, 129638的方格数据3（L=15, A 个L形有一段比较窄，而机器就在L形较窄的一端，这就造成了浪费。算2形成的

5、遍历一般都是螺旋形这也是算法2 使用螺旋形遍历的一个原因。相比之下，算法1却完成得很出色，覆盖了面积为6854的方格，把能覆盖的地方都覆盖了数据明显，基本上与算法1相同。这个地图，最主要的就是要寻找一个最长的路径。算法12 到80000 以上。数据（和第4个数据的图是一样的，但是L 个人认为，这个数据的H设得过于大了，不管怎么做，都只能得到4855的覆盖面积数据6（L=2, BADEGFC这个数据的H较小，属于那利用好每一步移动的数据。最大的忌讳，就是不能走进A、B、C数据6（L=2, BADEGFC这个数据的H较小，属于那利用好每一步移动的数据。最大的忌讳，就是不能走进A、B、C最好的策略是

6、撇开ABCDG不管，用蛇行法遍历顶部和右边的区域，然后进入F，如果在将F 的油水榨干以后还有剩余的移动次数，就进入E区域。这种策略：算法1把“1046”下方的一块正方形遍历了下来，但是没有很好地利用上顶端和右边的空地，最后覆盖了面积为2074 的方格。算法2则更是愚蠢地将ABCD都遍历了一遍，形成了巨大的浪费，最后只覆盖了面积为1296的方格数据ECADB这幅地图虽然很小，但是比其他地图更难。地图属于浪费分支较多的狭长通道型地图。A区域看似面在左侧的狭长通道和D、E。算法12 都不理想。算法1ED做到的最优的 是 154，可以用搜索算法获得。数据（L=2, EAF为主的地图，但又以空地E为关键

7、点。在区域A，只要进行必要的移动即可BCD EAF为主的地图，但又以空地E为关键点。在区域A，只要进行必要的移动即可BCD三个 1完全相同，因此算法1的到了最优解2004。而算法2就差一些，机器先进入了F，在F遍理结束，入E 的时候，在F 数据9（L=5, BA这个数据并不难。H A 区域和底部的弯曲通道，直接进入B 好的结果。算法12覆盖的面积分别是1252512456数据10（L=3, ECD AB这幅地图中，区域A和B面积都很大，可惜无法到达。区域C要好好利用。区域D算法1 遍历了D BCF 的小空地，最终的结果是21950。要好好利用。区域D算法1 遍历了D BCF 的小空地，最终的结

8、果是21950。算法2 同样 DCBAE 域不过，最优的办法并非一定要如此，可以绕着墙走一圈，好好利用B区域，然后再进入A 区域。这种方案可以保证不重复走任何一个方格。C 区域不宜进入，除非能够保证进去就不再回头，一旦回头就会在D、E造成浪费。算法1没有获得最优解，它遍历A区域时产生了一些浪费，最终的覆盖区域是1937。算法2要差一些，它的策略是绕着地图边界走，但是并没有好好利用B区域，且对C区域的处理方法不当12自测数据这个数刁难的地方，主要就Test_creator 写了几个字。这个图的特点是：空地 为什么不能覆盖所有区域呢？因为大多数难度较高的数据，都是H较小H较小的情况下，管它会造成浪

9、费1、2的策略进行移动13自测数据3（100*100L=5,这个数据也很简单，地图就是一个螺旋13自测数据3（100*100L=5,这个数据也很简单，地图就是一个螺旋形的“死胡同定的通路的宽度正好是 L+1,主要H 较小，所以，只要顺着道路向螺旋的中 域。5，黑色箭头代表机器移动方向域代表未清扫的区域。有的程受这个未清扫 图 盖了面积为469714自测数据4（500*500L=11 算法1发挥得还不错，覆盖了面积为107216 的方格；算法2 并没有想象得那样出色，覆盖区域的总面只有105467。估计是由于散点分布不规则，致使机器经常走进死胡同所造成的。15自测数据5（300*300，L=2

10、同，要想回头，就要付出巨大代价，但经常又不得不回头。主要的空地，就是A、B、C、D4 个区域，其中尤以C和D最为重要（C处于一个环形通路之中，走回头路时浪费小；通向D的通道则比较宽，也利理想，算法2的效果比算法1好一些，它们覆盖的面积分别和。DABC16自测数据6（100*100，DABC16自测数据6（100*100，L=2A 小，算法2与正确移动方向的一个巧合而已，如果向下走能覆盖的面积17自测数据7（100*100，L=5这个数据，主要用于考验程序是否能够好好利17自测数据7（100*100，L=5这个数据，主要用于考验程序是否能够好好利用第2、3行的城垛状缺口。在许多情况下，如果H 较

11、小，利用这种缺口往往会造成浪费。而这个数据恰恰相反，如果不利用缺口，一般都没有走完H步，那时算法1 和算法2 4031 407218自测数据8（100*100，L=2（地图与自测数据7相同这个数据将L变小，H变大。可以说，这时所有的城垛状缺口都不再是浪费性质的分支，机器要做的 是4633。19自测数据9（100*100，L=3这个数据，关键就在于A 区域。B C ，需要的步数小于HC 域之前，能够对A 区域形成较好的覆盖，最终的结果就会比较好。如果没有有效覆盖A 区域，进入了这种数据显然是算法1的弱项，最后覆盖面积为50792 略好5121。两个算法都对A区域利用得太少了。BAC20自测数据1

12、0（200*200L=8, 算法1覆盖面积为29756，算法23096420自测数据10（200*200L=8, 算法1覆盖面积为29756，算法2309641 说算法1 的毛病就在成了浪费。但是，在H较大时，它往往比算法1更能利用好所经过的空地。因此，算法21 视型”算法带来的浪费就越大；在H较大的时候，离起点越近，给“远视型”算法带来的浪费就越大“远视型”算法的浪费问题。曾经想过两种方法，一是通过地图的总面积与H 的大小关系，来判断应该是否进入缺口，但后来发现是否进入缺口并不仅仅取决于H与地图面积之间的关系，加上这个判以后，效果反而更差了；第二种方法，就是刚开始还是一如既往地向目标进发，以

13、后如果要补救缺口，必让机器赶回去，而是调整缺口旁边的移动方案，这样浪费的步数就大为减少整的缺口非常多，它们的价值又各不相同，如果每次都寻找价值最大的缺口来调整移动方案，时间上就优，不知道为什么地以后不再出来，两种方法是没什么区别的。如果进入空地以后还要出去，螺旋法，一般来说会终止于地确定好出口，然后沿着空地的边界走到出口的对面，再开始蛇行（如图6）。我在上面如图7，首先用BFS找出到起地以后不再出来，两种方法是没什么区别的。如果进入空地以后还要出去，螺旋法，一般来说会终止于地确定好出口，然后沿着空地的边界走到出口的对面，再开始蛇行（如图6）。我在上面如图7，首先用BFS找出到起点S 距离最远的点T，将从S到T 的路线作为初始路线。然后路 动次数的代价增加2。取增加面积最多的一段进行改进，得到一个改进线路。然后对改进线路同样进行类似的操作，如此循环往复，最后就可以得到一条长度为H的