ACM-ICPC 2010国内予選 D. ぐらぐら

D. ぐらぐら

解法

• 仕様どおりに実装するだけの簡単なお仕事
• 以下の実装では、再帰を使った深さ優先探索を行っている
  • isStable:(_y, _x)の位置にあるピースが安定ならtrueを返す
  • Mは関係するピースの座標値(+0.5)の合計
  • cntは関係するピースの個数
  • 重心のx座標はM/cntだけど、なんとなく整数のまま安定判定をしてみた
  • 上にピースが乗っていれば，安定性を調べつつMとcntを更新する

#include <iostream>
#include <string>
#include <queue>

using namespace std;

char dx[] = {0, 1, 0, -1};
char dy[] = {1, 0, -1, 0};

int w, h;
string s[60];
bool check[60][10];

bool isStable(int _y, int _x, int *rootM, int *rootCnt){
    bool res = true;
    int M = 2, cnt = 4, XL = 100, XR = -100;
    queue< pair<int, int> > qu; qu.push(make_pair(_y,_x));
    while(!qu.empty()){
        pair<int, int> p = qu.front(); qu.pop();
        int y = p.first, x = p.second;
        if(check[y][x]) continue;
        check[y][x] = true;
        M += x;
        if(y==h-1||(s[y+1][x]!='.'&&s[y+1][x]!=s[y][x])){
            XL = min(XL, x  );
            XR = max(XR, x+1);
        }
        if(y!=0&&!check[y-1][x]&&s[y-1][x]!='.'&&s[y-1][x]!=s[y][x])
            if(!isStable(y-1, x, &M, &cnt)) return false;
        for(int k=0;k<4;k++){
            int ny = y+dy[k], nx = x+dx[k];
            if(ny<0||h<=ny||nx<0||w<=nx) continue;
            if(s[ny][nx]=='.'||s[ny][nx]!=s[y][x]) continue;
            qu.push(make_pair(ny, nx));
        }
    }
    *rootM   += M;
    *rootCnt += cnt;
    return cnt*XL < M && M < cnt*XR;
}

int main(){
    int dM, dC;
    while(cin >> w >> h, w){
        for(int i=0;i<h;i++) cin >> s[i];
        memset(check, false, sizeof(check));
        for(int i=0;i<w;i++)
            if(s[h-1][i]!='.'){
                printf("%sSTABLE\n", isStable(h-1, i, &dM, &dC) ? "" : "UN");
                break;
            }
    }
}