No testdata at current.
题解:BFS求最短路(三维)
与一般的BFS求最短路相比,多了一维,一般只需要定义两维,比如dist[i][j]
表示到达(i,j)
点的最短时间,本题多了一个限制,状态,因此可以定义三维dist[i][j][k]
表示到达(i,j)
且状态为k
的时候的最短时间,本题与正常的上下左右四个方向相比,还多了一个原地踏步(就是坐标不变,但是状态会变)
在判断能否往(a,b)
点走时,也需要根据到达(a,b)
点的状态判断当前状态是否有障碍物,如果没有,才可以到达
C++
本题属于以下题库,请选择所需题库进行购买