UVa 1600 巡逻机器人（Patrol Robot）

一个机器人从网格左上角出发前往右下角，在这个过程中需要避免连续穿越k个带有障碍物的相邻单元。其中可用区域标记为0号单元而障碍物则标记为1号单元。每次移动一步，并且只能朝上下左右四个方向移动。要求计算最短路径长度，并且起点和终点均为可用区域

要点；

• 看起来似乎不复杂的问题，在编程实现时却并非易事。我们需要利用BFS算法计算最短路径，并在状态记录中增加一个字段来存储已经过的障碍物数量。具体来说，在扩展节点时若当前路径上的已过障碍物数超过k，则该路径不可行；否则我们继续扩展该节点，并将路径上的已过障碍物数加一；当处理完当前节点后将其标记为零个障碍物。
  • 然而这种做法存在不足之处：为了防止重复访问导致的时间超限（TLE），我们需要对访问过的格子进行标记（即vis数组）。然而这可能导致某些原本可以通过较少障碍物到达目标点的路径被忽略掉。
  • 这里的问题描述略显模糊：当经过不同数量障碍物到达同一个点时（即走过不同多边形边界的两种情况），你可能会选择之前走过更多边界的方式进行移动（因为此时已经被标记为已被访问过），而放弃原本可以通过较少边界到达该点的方式。因此一种可行的方法是使用优先队列来进行状态扩展
  • 使用优先队列可能会导致层次遍历无法高效完成：因为每次处理的时候都会先处理那些经过较少障碍物的状态（当然这也可以通过检查x+y值来实现判断）。但本人采用了不同的方法来处理这