hzCPPOJ

沉香的迷宫

时间限制:  1 s      内存限制:   128 MB
提交:7     正确:0     分值:100

题目描述

话说沉香长大后,拜霹雳大仙为师,学得一身高强的本领。向师父辞行,要去华山救母。霹雳大仙赠给他一柄萱花开山神斧以及一个锦囊,说这把神斧可以劈开大山,而这个锦囊在危机之时可以救你。

二郎神得知沉香去华山,施法在沉香必经之地变出一个巨大的湖,湖中长有许多参天大树,每棵数都有500丈高,50丈粗,组成一个巨大的迷宫。沉香停留了很久也没有走出迷宫,急得他哭了起来。湖里的水神听见哭声,浮出水面,一眼认出沉香,早有听说他是去救母,就想帮帮他。于是,水神来到沉香面前,温和地说:“这个大树迷宫是你舅舅故意布下的,就是想阻止你去华山救母。这些树有些是真树不能过,而有些是假树可以过的。”

沉香含泪问道:“请问神仙,怎么可以直到是真树还是假树呢?”

水神道:“真树和假树外形长的一模一样,二郎神也怕自己搞不清楚,所以他在施法时,偷偷在树上做了记号,第一个树杈画有@表示假树可以通行,#表示真树不能通行,画有就是这个迷宫阵的入口,画有符号的就是迷宫的出口。

水神又道:“二郎神为了让人无法通过,就让这个迷宫每隔3个时辰变换一种阵型,阵型有大有小,有些阵型在入口和出口之间是有通道存在的,是真出口,而有些阵型的入口和出口之间是没有通道存在,是假出口”

沉香急着问:“请问神仙,那有什么办法能走出这个迷宫吗?”

水神拿出一个类似镜子的东西说:“虽然这个迷宫变化很多、很难。但是,我这件宝贝,可以助你一臂之力。它能快速定位迷宫的入口,并判断迷宫的出口是真出口,还是假出口。只要是迷宫有真出口,你再记住我传给你的找路口诀,你就可以走出迷宫了。”

沉香听了大喜,又问:“神仙,找路口诀又是什么,快快告诉我吧。”

水神笑道:“你可挺好了,我只说一次:从入口开始,每次只能在当前位置,沿着东西水平方向或者南北垂直方向去找,遇到假树从它中间穿过,遇到真树不可过。“

沉香收下宝贝,谢过水神,然后按照水神教授的办法,终于走出了迷宫,继续向华山进发救母。

现我们用计算机来模拟沉香收到的宝贝如何判定真出口(入口和出口之间是连通的)还是假出口(入口和出口之间是不连通的)。其中用N,M表示迷宫的大小,用S表示迷宫的入口,D表示迷宫的出口,@表示假树可以通行,#表示真树不能通行。

输入

1行输入:迷宫规模NM,其中N,M取值范围为[5,10]

2行开始,输入N行,每行M个树的符号 

输出

如果是真出口输出T,如果是假出口输出F。

样例

样例输入:
5 5 @@#@@ @@#@@ @S@@@ @@@#@ @D@@@
样例输出:
T
样例输入:
5 5 @#@@@ # S #@@ @#@#@ @@#@@ @@@D@
样例输出:
F

提交人

spiritatu