#include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <string> using namespace std; // 全局变量（简化递归传参） int n, m; vector<vector<char>> grid; // 字符转移规则：key是当前字符，value是下一个目标字符 unordered_map<char, char> next_char = {{'L', 'Q'}, {'Q', 'B'}, {'B', 'S'}, {'S', 'L'}}; bool has_infinite = false; // 标记是否存在无限循环 // 记忆化缓存：key是状态字符串（i,j,target），value是该状态的最大次数 unordered_map<string, int> dp; // 递归路径标记：记录当前正在访问的状态，用于检测环 unordered_set<string> visited; // 生成状态字符串（i,j,target），作为map/set的key string getState(int i, int j, char target) { return to_string(i) + "," + to_string(j) + "," + target; } // DFS函数：返回从(i,j)出发，当前目标字符为target时的最大LQBS次数 int dfs(int i, int j, char target) { // 1. 边界判断：坐标越界 或 当前字符不匹配目标，返回0 if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != target) { return 0; } // 2. 生成当前状态key string state = getState(i, j, target); // 3. 检测环：如果当前状态在递归路径中，说明无限循环 if (visited.count(state)) { has_infinite = true; return -1; } // 4. 记忆化：如果已计算过该状态，直接返回结果 if (dp.count(state)) { return dp[state]; } // 5. 标记当前状态为正在访问 visited.insert(state); int max_count = 0; // 上下左右四个方向 vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (auto& dir : dirs) { int ni = i + dir.first; int nj = j + dir.second; char next_target = next_char[target]; // 下一个目标字符 int res = dfs(ni, nj, next_target); if (has_infinite) { // 发现无限循环，直接返回 return -1; } // 6. 计数规则：只有S→L时，完成一次LQBS，次数+1 if (target == 'S') { max_count = max(max_count, res + 1); } else { max_count = max(max_count, res); } } // 7. 移除当前状态的访问标记（递归回溯） visited.erase(state); // 8. 缓存当前状态的结果 dp[state] = max_count; return max_count; } int main() { // 1. 读取输入 cin >> n >> m; grid.resize(n, vector<char>(m)); for (int i = 0; i < n; ++i) { string line; cin >> line; for (int j = 0; j < m; ++j) { grid[i][j] = line[j]; } } // 2. 遍历所有L的位置作为起始点 int max_result = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] == 'L') { // 每次DFS前清空路径标记（避免不同起始点的状态冲突） visited.clear(); int current_res = dfs(i, j, 'L'); if (has_infinite) { cout << -1 << endl; return 0; } max_result = max(max_result, current_res); } } } // 3. 输出结果 cout << max_result << endl; return 0; }