TODO 调试 PAT 甲级 1007

最近在重拾算法刷题,遇到测试用例通不过的情况,还是第一次在博客上写TODO,要新建一个TODO标签了,希望之后记得解决。

解决这个问题倒也有通用的思路:就是写一个随机的测试用例生成程序,模拟一些限定范围内的输入数据,用正确的程序跑,得到正确的结果,<随机输入,正确的输出>就是一个测试用例了,用来测试编写的程序。

这个工具我计划实现一下,应该会事半功倍,其中有一层要抽象的是输入数据之间的关系,这个想要做得好用,得配上一个Web界面,支持一些常用输入关系的配置。

[搜索]奥特曼打怪兽

题目描述

奥特曼是正义的化身,现在奥特曼需要消灭地图中所有怪鲁,该地图由一个M×M的矩阵组成,地图中的怪兽有不同的难度级别。
0表示陷阱,不能进入
1表示陆地,可以通过
大于等于2的正整数表示各种级别的怪兽,数字越大表示怪兽越强。
现在奥特曼需要按照级别从弱到强消灭地图中所有的怪兽,怪兽一旦被消灭,怪兽所在的地方就变回为陆地。
奥特曼从原地开始(0,0)行动,在地图中只能上下左右移动,那么奥特曼最少需要走多少步才能消灭所有怪兽, 如果无法消灭所有怪曽返回-1。
约束:
1.地图中不会有级别一样的怪兽
2.不允许宾特曼经过一个怪兽而不消灭它
输入描述:
一个由M×M构成的炬阵,3≤M≤50,该矩阵每行数字之间用空格隔开
输出描述:
如果奥特曼能够依次消灭所有怪兽,输出最小步数,如果无法全部消灭输出-1。

输入样例

输出样例

思路描述

乍一看,是到搜索题。

等我跑步回来写……

方法一:BFS

方法二:DFS

测试输入用例(不全)

总结

  • 无论是BFS还是DFS都不适用于地图变化的情形,所以要转换为地图不变的问题来处理。比如,明确“起点”、“终点”。
  • 明确好“岔道口”和“死胡同”在题目中的指代,即可转换为搜索问题。当然这道题还算明显。

Lucas定理与大组合数的取模的求法总结 - pi9nc的专栏 - CSDN博客

对Lucas定理的能力范围,我需要实验求证一下。

Lucas最大的数据处理能力是p在10^5左右,不能再大了,hdu 3037就是10^5级别的!

来源: Lucas定理与大组合数的取模的求法总结 - pi9nc的专栏 - CSDN博客