A0450 [BJ2014.X5] 迷宫(GOOD)

#include <bits/stdc++.h>
using namespace std;

// 迷宫里三种格子：'.' 空地，'#' 墙壁，其余（'*' 或 '✻'）是陷阱。
// 题面描述用 '✻'，样例里用 '*'，所以只要不是 '.'/'#'/'S'/'E' 一律当陷阱。

int n, m;
vector<string> g;
int sx = -1, sy = -1;

// 把一行原始字节解码成 m 个格子：ASCII 字符各占一格，
// 多字节的 UTF-8 字符（'✻'）整体算一格（陷阱）。
string decodeRow(const string &s) {
    string out;
    for (size_t i = 0; i < s.size();) {
        unsigned char c = (unsigned char)s[i];
        if (c < 0x80) {
            out += s[i];
            i++;
        } else {
            out += '*';
            i++;
            while (i < s.size() && ((unsigned char)s[i] & 0xC0) == 0x80) i++;
        }
    }
    return out;
}

// 从起点做一次广搜。allowTrap 为真时可以踩陷阱。
// visited 按“第几步被访问”记录，便于演示展开过程。
vector<vector<int>> reachOrder(bool allowTrap) {
    vector<vector<int>> vis(n, vector<int>(m, 0));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[nx][ny]) continue;
            if (g[nx][ny] == '#') continue;
            if (!allowTrap && g[nx][ny] != '.' && g[nx][ny] != 'S' && g[nx][ny] != 'E') continue;
            vis[nx][ny] = vis[x][y] + 1;
            q.push({nx, ny});
        }
    }
    return vis;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        g.push_back(decodeRow(s));
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'S') { sx = i; sy = j; }

    auto vis = reachOrder(false);
    bool good = false;
    for (int i = 0; i < n && !good; i++)
        for (int j = 0; j < m && !good; j++)
            if (g[i][j] == 'E' && vis[i][j]) good = true;
    if (good) {
        cout << "GOOD\n";
        return 0;
    }

    vis = reachOrder(true);
    bool ok = false;
    for (int i = 0; i < n && !ok; i++)
        for (int j = 0; j < m && !ok; j++)
            if (g[i][j] == 'E' && vis[i][j]) ok = true;
    cout << (ok ? "OK" : "BAD") << "\n";
    return 0;
}