迷宫之深度搜索

Jobdu-1461

题目大意：有一个N*M的迷宫，包括起点‘S’,终点‘D’，墙‘X’和地面‘.’。0秒时主人公从S出发，每秒只能走到四个相邻位置中的一个，且走过的路线不能再走。问是否存在一条路径，使得主人公刚好在T秒时走到D。

最优解问题一般用广搜，而判断是否有解时可用深度优先搜索。

确定状态三元组（x,y,t)。(x,y)为当前点坐标，t为时刻。初始状态为（起点x，起点y，0）。

样例输入：

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

样例输出：

NO
YES

最后更新：2017-04-03 12:55:13