python/TangDou/Bfs/4_LQBS.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
char a[N][N];       //地图
struct Node {
    int x;
    int y;
    int step;
};
queue<Node> q;
string S = "LQBS";  //行进路线

int dx[] = {-1, 0, 1, 0};   //左上右下
int dy[] = {0, 1, 0, -1};

int step;       //移动步数
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 'L') {
                q.push({i, j, 1});
                while (q.size()) {
                    auto t = q.front();
                    q.pop();
                    char c = a[t.x][t.y];
                    int pos = S.find(c);
                    char next = S[(pos + 1) % 4];

                    for (int k = 0; k < 4; k++) {
                        int x = t.x + dx[k], y = t.y + dy[k];
                        if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == next) {
                            q.push({x, y, t.step + 1});
                            step = max(step, t.step + 1);
                            if (step > 2 * n * m) {
                                printf("%d", -1);
                                exit(0);
                            }
                        }
                    }
                }
            }
        }
    //记录整数值，然后整除4取商即可
    printf("%d", step / 4);
    return 0;
}
/*
 4 4
BLQB
BBQS
SBQL
QQQQ
 */