6096: 蓝桥杯赛迷宫

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:7 Solved:3

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

样例2输入: 

3 3

LSB

QBQ

BSL

样例2输出: 

-1

 

样例3输入: 

4 4

BLQB

BBQS

SBQL

QQQQ

样例3输出: