No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

我们先来玩一个迷宫游戏，尝试走一下面的迷宫。

思考:在走迷宫问题里面的状态应该怎样表示？

这是一种最短的走法：

接下来，我们通过一个实际问题——《迷宫游戏》来学习深度优先搜索（dfs）。

迷宫b游戏

我们用一个二维的字符数组来表示前面画出的迷宫：

S**.
....
***T

其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。

我们首先考虑状态:在走迷宫问题中，状态的表示应该是当前所在的点的坐标 (x, y)。初始的时候我们在起点S处，之后我们进行我们的搜索过程，也就是我们要讲的dfs算法。

首先我们把现在所在的点的坐标称为当前状态，它初始时在起点处。我们首先要判断当前状态是否为终点，若为终点就表示我们成功完成了这个问题，否则我们按照左、下、右、上的顺序， 依次 判断"当前状态"的相邻点是否 合法。如果"当前状态"的左、下、右、上四个点中的 某一个点合法 ,我们就将这个点作为 新的 "当前状态"，对于这个状态重复本步骤。最后，如果某一个状态的左、下、右、上四个点都 不合法,那么我们就回退到这个状态的上一个状态，继续尝试其它路径。

基于这样的步骤，深度优先搜索一般使用递归实现，稍后我们将根据伪代码框架进行理解。

我们先来看在这个问题中关于合法状态的定义：

1. 必须在所给定的迷宫范围内。 如样例中是一个 4 行 3 列的迷宫，那么这个点必须在 $(0,0)-(3,2)$的范围中才能称为合法，否则即为不合法。
2. 这个点在本次搜索中必须没有被访问过。 也就是说，一个点在dfs的时候只能被访问一次，不能重复访问。这样做是因为，如果一个点允许多次访问，那么肯定会出现死循环的情况——在两个点中间来回走。不过，根据题意，在某些情况下，你回溯了之后可以视回溯前的点为没有访问过。
3. 这个点必须不是墙壁。这个显然很好理解，我们只能走在平地上，不能走在墙壁上也不能穿过墙壁。

dfs 走迷宫对应的伪代码框架如下：

// 对坐标为 (x, y) 的点进行搜索
bool dfs(int x, int y) {
    if (x, y) 是终点 {
        // 找到了路径
        return true;
    }
    标记 (x, y) 已经访问
    向上走到位置 (tx, ty)
    if (tx, ty) 合法 {
        if (dfs(tx, ty) == true) {
            // 递归调用dfs函数，将(tx, ty)作为当前状态进行搜索，下同。
            return true;
        }
    }
    向左走到位置 (tx, ty)
    if (tx, ty) 合法 {
        if (dfs(tx, ty) == true) {
            return true;
        }
    }
    向下走到位置 (tx, ty)
    if (tx, ty) 合法 {
        if (dfs(tx, ty) == true) {
            return true;
        }
    }
    向右走到位置 (tx, ty)
    if (tx, ty) 合法 {
        if (dfs(tx, ty) == true) {
            return true;
        }
    }
    return false;
}