《逃离迷宫II》题目分析

本题是一道宽搜题目。这类题目的关键在于设计合适的状态表示。

比如本题的状态可以用三元组表示，即处在迷宫第i行第j列，并且面朝方向k(k=0~3，表示上下左右四种方向）。

假设当前状态是，位置(i, j)沿着k方向走一格会到达(ni, nj)。如果(ni, nj)是空地，那么就只有一条连向的边，并且由于不需要转向，边的权值为0；否则会有4条边分别连向, , , ，边权值都是1。

对于这样边权为0/1的图，找最短路可以用双端队列来实现。

具体来说，每次从队首拿出当前状态，扩展出所有后继状态。如果边权为0，相应的后继状态就从队首加入；如果边权为1，就从队尾加入。同时我们要判重，不让重复状态进队。

这样找最短路的时间复杂度是O(N^2)的。