bfs就是宽度优先搜索,用到队列来保持一个先入先出的结构,队列开的长度应该是边长的平方表示的是全部点的个数,存的是位置,所以可以是用pair<int, int> 来存,

其中用组数模拟队列的方法就是定义两个指针,hh、tt ,hh = 0, tt = -1,存入元素时,++tt ,表示向后退一格,弹出队头时hh++,表示同时退后一个元素,同时原来的索引就不用管了,为的是节约时间,但是可以浪费一点内存

这样是为了,在后面加入的元素时可以优先把前面先加入的元素进行宽搜,为了标记位置是否已经来过,需要一个bool二维数组来储存,同时用一个int类型的二维数组来储存每一个点是第几个经过的点,当这个点是终点时,也就是成了从初始点到终点的距离,所以显然,初始点的值为0,表示还没有开始走,也就是头节点。因为是对没有个节点进行标记,所以第一次到达终点时,就是最短的路径,因为有队列在保持后面相同同一层的点,假如某一点要再走两格才可以到达,但是第一个点,就是我们拿出来的头节点可以在下一次的遍历中就到达终点,并给终点上了个标记,所以很显然就是,这个第一次经过的终点距离是最短的。

用来模拟向四个方向走可以新建两个数组,表示偏移量,例如dx = {-1,0,1,0},dy = {0,1,0,-1},分别表示(-1,0)、(0,1)、(1,0)、(0,-1),即向上,向右,向下,向左
之后只要for循环4次,表示四个坐标,同时加上限制条件(边界或其他),如果满足条件,则那个点的路径数为前面的路径数 + 1,然后将其放到对列中

所以为了保持这个最短的性质,每次再加入队列之前先进行判断是不是已经经过了,如果已经经过了就没有必要再经过一遍,所以就不用加入队列,从而有了一个循环结束的标志,就是当队列中没有元素时,即没有新的元素加入,然后老元素也已经全部走完时,就是表示表格中的所有元素都被走过了,此时输出终点的路径数就是最短路径数

关于输入以及边界判断,如果主要是看题目,来看是从1开始还是从0开始。以及对应的终点的坐标是否要减1

关于如何输出路径,可以再新建一个类型为pair<int, int> 类型的二维数组pre,来存放每个点之前的坐标,然后在输出的时候,可以用一个while循环来表示,while(x || y) 表示当x或y有一个不为0时,循环就继续,即如果x和y都为0时循环就结束,在逻辑上就是起始点没有前一个点,然后在每次进行扩张的时候都将当前点的上一个存入pre。

思考:这个时候如果已经知道了终点的坐标,而且只有一个询问,是不是可以在当循环遍历到终点时就return,但是如果是有多组询问,或许应该就是要让他bfs跑完,这样的话每次查询的时间复杂度就是O(1)的了。

标签: 无ai

添加新评论