迷宮之深度搜索

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