2433: LQ1101 迷宫 省赛

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

把一个 n 行 m 列的字符阵列看做一个迷宫，迷宫仅包含 L、Q、B、S 中的大写字母（蓝桥杯赛的汉语拼音首字母）。

初始时，你可以从任意一个“L”字母开始，移向相邻的“Q”字母，然后从此“Q”字母出发，移向相邻的“B”字母，然后从此“B”字母出发，移向相邻的“S”字母……。这样，你就算是走过了一个“LQBS”字符序列。

接下来，仍然可以从此“S”字母出发，移向相邻的“L”字母……，重复上述的动作，你就可以不断地走过“LQBS”序列。

请注意，所谓相邻仅包含上、下、左、右 4 个方向，且只能从 L->Q，从 Q->B，从 B->S，从 S->L。
可以想像，由于选择的出发点不同，我们有可能在迷宫中走过无数次的“LQBS”，或者是有限次的“LQBS”，
或者一次也走不了。

请你编写程序，求出在给定的迷宫中，我们最多可以走过多少次“LQBS”?

Input

第一行：正整数 n,m，表示迷宫的规模为 n 行 m 列，0<m<100，0<n<100
接下来的 n 行：每行 m 个符合题意的字母，字母间无空格。

Output

一个整数。
即：如果在迷宫中可以无限次的走过“LQBS”，输出-1，否则，输出可以走过“LQBS”的最多次数。

Sample Input Copy 

1 2
LQ

Sample Output Copy 

0

HINT

样例数据分析:
样例1:
第一行数据3 3 代表是3行3列的迷宫
第1步,寻找L
LSB
QBQ
BSL
第2步,在L的上下左右寻找Q
LSB
QBQ
BSL
第3步,在Q的上下左右寻找B
LSB
QBQ
BSL
第4步,在B的上下左右寻找S
LSB
QBQ
BSL
如此当重复到10次的时候,仍可以继续走,代表进入无限循环
因为3行3列最多9个格子,能走10步就代表一定进入无限循环
输出-1
样例2:
第一行数据4 4 代表是4行4列的迷宫
第1步,寻找起点L
BLQB
BBQS
SBQL
QQQQ
第2步,在L的上下左右寻找Q
BLQB
BBQS
SBQL
QQQQ
第3步,在Q的上下左右寻找B
BLQB
BBQS
SBQL
QQQQ
第4步,在B的上下左右寻找S
BLQB
BBQS
SBQL
QQQQ
第5步,在S的上下左右寻找L
BLQB
BBQS
SBQL
QQQQ
第6步,在L的上下左右寻找Q
BLQB
BBQS
SBQL
QQQQ
第7步,在Q的上下左右寻找B
BLQB
BBQS
SBQL
QQQQ
第8步,在B的上下左右寻找S
BLQB
BBQS
SBQL
QQQQ
第9步,在S的上下左右寻找L
因为找不到L了,则代表迷宫走到尽头,一共走了8步,LQBS一共4个字符,所以走了
8/4=2共计2次LQBS,输出2

Source/Category

SubmitSubmit RecordStatisticsShowOff!