AHUCM Online Judge

问题1137--初火降临与巨龙时代的终结（II）

1137: 初火降临与巨龙时代的终结（II）

_{[命题人 : ]}

时间限制 : 1.000 sec 内存限制 : 128 MB

提交

解决: 2 提交量: 2 统计

题目描述

这个世界本由巨龙所统治，它们早在人类、甚至火焰诞生之前就已经存在。空间中只有灰蒙蒙的迷雾和巨大的石树，巨龙逡巡其间，人类尚未诞生。巨龙的统治持续了很长时间，为这些巨大的蜥蜴敲响丧钟的事件是“初火”的降临。火是一种神奇的力量，它为这个世界带来了光明和黑暗。在黑暗之中，类人生物诞生了，这些拥有智慧的生物在火中发现了魂，而其中最重要的，是“伟大的灵魂”与“黑暗之魂”。其中伟大的灵魂分别由太阳王格温、墓王尼特、伊扎里斯的魔女（所获得，黑暗之魂则由 “鬼鬼祟祟的矮人”所获得。

输入

给出一个N 表示矩阵的列数和列数(也就是方阵了), N<=10。

每个测试点一个矩阵，判断主角用表示能不能走到篝火处，用H表示。主角可以往上下左右四个方向走，但是不能斜着走。同时也不能走出地图，和穿过障碍物（使用“X”表示）。普通地形使用‘N’表示。

输出

注意：规定 DFS 的方向为 int dirs[][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };

如果主角可以抵达篝火，那么输出所有可以达到篝火的路径（格式参考样例输出），如果不能抵达篝火，输出 “前无篝火”

样例输入 Copy

4
XXXX
NHNN
NNNN
NNFN

样例输出 Copy

(1,1)->(2,1)->(3,1)->(3,2)
(1,1)->(2,1)->(2,2)->(3,2)
(1,1)->(2,1)->(2,2)->(1,2)->(1,3)->(2,3)->(3,3)->(3,2)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)
(1,1)->(2,1)->(2,0)->(3,0)->(3,1)->(3,2)
(1,1)->(1,2)->(2,2)->(3,2)
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)
(1,1)->(1,2)->(2,2)->(2,1)->(3,1)->(3,2)
(1,1)->(1,2)->(2,2)->(2,1)->(2,0)->(3,0)->(3,1)->(3,2)
(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(3,2)
(1,1)->(1,2)->(1,3)->(2,3)->(2,2)->(3,2)
(1,1)->(1,2)->(1,3)->(2,3)->(2,2)->(2,1)->(3,1)->(3,2)
(1,1)->(1,2)->(1,3)->(2,3)->(2,2)->(2,1)->(2,0)->(3,0)->(3,1)->(3,2)
(1,1)->(1,0)->(2,0)->(3,0)->(3,1)->(2,1)->(2,2)->(3,2)
(1,1)->(1,0)->(2,0)->(3,0)->(3,1)->(2,1)->(2,2)->(1,2)->(1,3)->(2,3)->(3,3)->(3,2)
(1,1)->(1,0)->(2,0)->(3,0)->(3,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)
(1,1)->(1,0)->(2,0)->(3,0)->(3,1)->(3,2)
(1,1)->(1,0)->(2,0)->(2,1)->(3,1)->(3,2)
(1,1)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)
(1,1)->(1,0)->(2,0)->(2,1)->(2,2)->(1,2)->(1,3)->(2,3)->(3,3)->(3,2)
(1,1)->(1,0)->(2,0)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)

提示

DFS + 记忆化

来源/分类

提交