[搜索]奥特曼打怪兽

题目描述

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

输入样例

输出样例

思路描述

乍一看,是到搜索题。

等我跑步回来写……

方法一:BFS

方法二:DFS

测试输入用例(不全)

总结

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

发布者

Jiaheng Tao

挖掘概念,创造工具

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据