#7556. 【提高】蓝桥杯 迷宫 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

把一个 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”?

输入格式

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

输出格式

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

样例

样例输入1

1 2
LQ

样例输出1

0

样例输入2

3 3 
LSB 
QBQ 
BSL

样例输出2

-1

样例输入3

4 4 
BLQB 
BBQS 
SBQL 
QQQQ

样例输出3

2