资源描述：
《北京大学ACM国际大学生程序设计竞赛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、问题求解与程序设计 第七讲 搜索李文新2004.2–2004.6内容提要搜索讨论1011stick讨论1054thetroublesomefrog参考王知昆的冬令营报告作业搜索的一般概念在解空间中尝试所有可能，找出满足条件的取值回顾填数游戏：1-9填在3*3的表格中，使得行、列、对角线的和均为15。方程组搜索–逐一尝试+剪枝题目讨论1011stick题目讨论TheTroublesomeFrogIOI2002day1task1问题稻田问题青蛙从外面跳入稻田，踩过一些禾苗，后，跳出稻田。问题蛙路：一个方向，等间距，大于等于3个点不同蛙路：可以方
2、向不同，间距不同问题许多青蛙跳过稻田，形成多条蛙路，不同蛙路可以踩过同一作物。问题青蛙每天早上踩坏稻田，早上人们发现稻田有若干株作物被踩坏，但不知多少青蛙来过。也有不在蛙路上的被踩坏的作物。问题问，给定一块被踩坏的稻田，求可能的最长的蛙路上被踩坏的作物的数目。输入第一行整数R和C，稻田的行数和列数第二行整数N，表示被踩坏的作物总数。后续N行，每行两个整数i,j为被踩坏的作物的行和列的位置:1<=i<=R,1，1<=j<=C。每个被踩坏的作物只出现一次。输出单个整数--表示最长可能蛙路上踩坏的作物数目样例Figure-4问题的解这道题目也就是
3、说，在给出的n个点中找出一些点的序列来，使得每一个点相对于上一个点的坐标都是一个相同的向量，且第一个点减去这个向量和最后一个点加上这个向量后均落在方格的外面。问题的解我们先对这些点按照坐标排序。然后依次循环出要求的序列中的第一个和第二个点，这样我们就知道后一个点相对于前一个点的坐标是多少了。然后我们依次用第二个点加上这个坐标的出第三个点，第三个点加上这个坐标得出第四个点等等。当然，我们还需要判断一下这求出来的第三个、第四个点是否在给定的点内。问题的解由于每个点的上一个点/下一个点最多只能有n种选择，故一个点最多属于n条不同的蛙路。这样，对于
4、某个确定的点来说，它的所有可能的下一个需要判断的点至多有n个。这样因为判断一个点在不在给定的点内只需要O(1)的复杂度，所以我们只需要O(n2)的时间就可以得出问题的解答。由于这个算法需要一个r*c的表来保存点在方格中的存在状态，故空间复杂度为O(n2)。问题的解需要注意的是，蛙路中的点数少于3个的时候是不考虑的。所以这个时候的蛙路中的点数应该按照0来算。实现细节Frogvsfrog’平面上点的表示Frog2–0有冗余代码Frog2–1去掉冗余Frog2–2compare判断Frog2–3改变表达式写法Frog2–4增加剪枝Frog2–5不
5、太好的剪枝顺序Frog2–6较好的剪枝顺序测试数据No.N,(R*C)DescriptionSolution118,(6*7)Sampledatainthetaskdescription4210,(10*10)Manuallydesigned5325,(50*50)Manuallydesigned13450,(10*10)SeveralLines+randompoints105100,(20*20)modifiedrandompointset106300,(30*30)modifiedrandompointset157500,(55*55)
6、SeveralLines+randompoints288500,(100*100)Specialcasefornosolution091000,(100*100)SeveralLines+randompoints34101000,(1000*1000)SeveralLines+randompoints250112000,(50*50)Random(uniform)points25122000,(100*200)SeveralLines+randompoints33132000,(1000*2000)SeveralLines+randompo
7、ints333测试数据143000,(60*60)Uniformlyrandompoints31153000,(500*500)Xshapesandrandompoints500163000,(5000*1)Horizontalline20173000,(5*1000)SeveralLines+randompoints17184000,(100*100)Randompoints(uniformly)34194000,(200*20)Verydensepointsset200204000,(1000*1000)SeveralLines+ran
8、dompoints500214000,(5000*5000)SeveralLines+randompoints311225000,(100*100)Chessboardstyle
