AOJ 1168: ぐらぐら

これ全然むずかしくないし 250 くらいで良いのでは…？

問題

Off Balance | Aizu Online Judge

解法

言われたとおりやるだけです。

ブロックを上から調べていき, それが地面にどれだけくっついているのかを調べます。
また, そのブロックの上に乗っかっているブロックを全部調べます。

で, x 軸方向の重心が条件を満たすかを調べるだけです。
double 型だと気持ち悪いので, x 軸方向は 2 倍しておくと全部整数で処理できます。

int H, W;
string board[100];

vector<pii> getPos(char c, int sy, int sx) {
    vector<pii> ret;
    queue<int> que;
    que.push(sy); que.push(sx);
    ret.emplace_back(sy, sx);
    while (!que.empty()) {
        int y = que.front(); que.pop();
        int x = que.front(); que.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y+dy[i];
            int nx = x+dx[i];
            if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
            if (board[ny][nx] == c && find(ret.begin(), ret.end(), pii(ny, nx)) == ret.end()) {
                que.push(ny); que.push(nx);
                ret.emplace_back(ny, nx);
            }
        }
    }
    return ret;
}

bool ok() {
    for (int y = 0; y < H; y++) for (int x = 0; x < W; x++) {
        // c を探せ
        char c = board[y][x];
        if (c == '.') continue;
        vector<pii> ps = getPos(c, y, x);
        int xl = 100, xr = -1;
        for (pii p : ps) {
            int y = p.first, x = p.second;
            if (y == H-1) {
                xl = min(xl, 2*x);
                xr = max(xr, 2*x+2);
            } else {
                int ny = y+1;
                if (board[ny][x] != '.' && board[ny][x] != c) {
                    xl = min(xl, 2*x);
                    xr = max(xr, 2*x+2);
                }
            }
        }
        // cerr << c << " : " << xl << "  " << xr << endl;
        // ps に支えられているのを探せ
        vector<pii> up = ps;
        while (1) {
            bool finish = true;
            for (pii p : up) {
                int y = p.first, x = p.second;
                if (y==0) continue;
                char tmp = board[y-1][x];
                if (tmp == '.') continue;
                vector<pii> cs = getPos(tmp, y-1, x);
                assert(!cs.empty());
                if (find(up.begin(), up.end(), cs[0]) == up.end()) {
                    finish = false;
                    for (pii pp : cs) up.push_back(pp);
                    break;
                }
            }
            if (finish) break;
        }
        int sum = 0;
        for (pii p : up) {
            sum += 2*p.second+1;
        }
        if (sum <= xl * up.size() || sum >= xr * up.size()) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> W >> H) {
        if (H==0 && W==0) break;
        for (int i = 0; i < H; i++) cin >> board[i];
        if (ok()) cout << "STABLE" << endl;
        else cout << "UNSTABLE" << endl;
    }
    return 0;
}