from collections import deque def main(): import sys input = sys.stdin.read().split() idx = 0 n = int(input[idx]); idx += 1 m = int(input[idx]); idx += 1 maze = [] for _ in range(n): maze.append(input[idx]) idx += 1 # 字符映射到数字 char_map = {'L':0, 'Q':1, 'B':2, 'S':3} dirs = [(-1,0),(1,0),(0,-1),(0,1)] # 建图 + 入度统计 in_degree = [[0]*m for _ in range(n)] graph = [[[] for _ in range(m)] for _ in range(n)] for i in range(n): for j in range(m): cur = char_map[maze[i][j]] nxt = (cur + 1) % 4 for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < n and 0 <= nj < m: if char_map[maze[ni][nj]] == nxt: graph[i][j].append((ni, nj)) in_degree[ni][nj] += 1 # 拓扑排序队列初始化 q = deque() dp = [[0]*m for _ in range(n)] # 初始L的位置，次数为0（还没完成一次） for i in range(n): for j in range(m): if maze[i][j] == 'L': dp[i][j] = 0 q.append((i, j)) # 拓扑排序 + DP while q: i, j = q.popleft() for ni, nj in graph[i][j]: # 更新dp值 add = 1 if maze[ni][nj] == 'S' else 0 if dp[ni][nj] < dp[i][j] + add: dp[ni][nj] = dp[i][j] + add in_degree[ni][nj] -= 1 if in_degree[ni][nj] == 0: q.append((ni, nj)) # 检查是否有环（存在未处理的节点） for i in range(n): for j in range(m): if in_degree[i][j] > 0: print(-1) return # 找最大次数 max_cnt = 0 for i in range(n): for j in range(m): max_cnt = max(max_cnt, dp[i][j]) print(max_cnt) if __name__ == "__main__": main()