BFS虽然很熟练了但是做过的题都是一个状态在图里走来走去,意义不大。而关于多个状态在图里的遍历,虽然本质上没有区别,但是容易写挫而且码的时候思路容易混乱,今天就总结几道这样的题叭。
Bloxorz长方块游戏
题意
n行m列的矩阵,有硬地,易碎地面,禁地三种状态的地面.你需要将一个1 * 1 * 2的长方体通过上下左右四个方向的滚动移到终点,易碎地面不能保持站立,禁地不可触碰,否则都会掉下去.开始时可以任意摆放,但是结束时必须站立在终点.求最少需要移动几步?
思路
如果是一个正方体那么只需要遍历位置这一个状态,而本题需要将站立,水平,竖直摆放三种状态进行遍历,需要定义一个坐标和状态的三元组用bfs进行求解.
代码
1 | // 存放状态的三元组,左上的坐标和躺到的姿势 |
矩阵距离
题意
给定一个01矩阵,求每一个点到附近值为1的点的最短曼哈顿距离.
思路
用最朴素的想法就是把矩阵中的每一个点当作起点做一次BFS,当找到值为1的点时记录步数,但是这样的复杂度是不能接受的.反过来考虑,把每一个值为1的点当作起点,向外扩散找点,每当到达一个没有访问过的点时步数一定是最短距离.
代码
1 | int n, m, d[N][N]; |
Pushing Boxes
题意
一个推箱子游戏,要求求出从起点到终点最短的路径,包括箱子的路径和小人的路径.
思路
双重BFS,不得不说这道题很容易卡,尤其是要求输出推箱子的过程,找路径算是一个难点.大概有两种做法:
暴力一点直接双重BFS,每次先为箱子bfs找下一步,然后bfs求出小人到箱子旁边的路径存进去.每一个状态的移动记录相应的存进去.
更好地是在动规和搜索中经常用的递推找路径,先只对箱子BFS找路径,然后记录每一个位置是从哪个位置推过来的,然后按照运动轨迹倒着找回去,在相邻两个位置间对小人bfs即可,本题只实现了第一种做法.
PS:牛客上的这道题虽然来源于poj,但是输出格式不同,修改了之后还WA了,只能说牛客的数据有问题或者数据比较严叭…但是20*20的图能有什么数据???郁闷.
代码
1 | struct node { |