1168 ぐらぐら
ほうしん
まず番号がかぶっているブロックがあるので、番号を振り直す。
そのときついでに、自分の上に乗っているブロックと自分が他のブロックまたは地面と接している部分を求めておく。
一番下の地面に接しているブロックから順に、自分と自分の上に乗っている全てのブロックをあわせた全体の重心を再帰的に求める。
最後に、もう一度再帰的に全てのブロックが安定しているかチェックする。
実装つらすぎる・・・
ソース
#include<iostream> #include<cstring> #include<string> #include<vector> #include<map> #include<queue> #include<algorithm> using namespace std; #define REP(i,a,b) for(i=a; i<b; ++i) #define rep(i,n) REP(i,0,n) string input[90]; int in[90][20]; bool visited[90][20]; struct Block { vector<pair<int,int> > blocks; int num,bl,br,xsum; vector<int> above; double G; void getG() { int sum = 0; for(int i=0; i<blocks.size(); ++i) sum += blocks[i].second; xsum = sum+2; } }; int dx[4] = {0, -1, 0, 1}; int dy[4] = {1, 0, -1, 0}; bool rec(int pos,vector<Block> &bv) { int i; rep(i,bv[pos].above.size()) if(!rec(bv[pos].above[i], bv)) return false; if(bv[pos].bl >= bv[pos].G || bv[pos].br <= bv[pos].G) return false; return true; } //calc centroid pair<int,int> calcG(int pos,vector<Block> &bv) { int bcount = 4, i, Gsum = bv[pos].xsum; rep(i, bv[pos].above.size()) { pair<int,double> tmp = calcG(bv[pos].above[i], bv); bcount += tmp.first; Gsum += tmp.second; } bv[pos].xsum = Gsum; bv[pos].G = (Gsum/(double)bcount); return make_pair(bcount, Gsum); } int main() { int w,h,i,j,k; while(cin>>w>>h, w|h) { rep(i,h) cin>>input[i]; memset(in, -1, sizeof(in)); memset(visited, false, sizeof(visited)); vector<Block> bv; int bnum = 0; rep(i,h) { rep(j,w) { if(input[i][j] != '.' && !visited[i][j]) { Block tmp; queue<pair<int,int> > Q; Q.push(make_pair(i,j)); tmp.blocks.push_back(make_pair(i,j)); tmp.num = bnum++; visited[i][j] = true; while(!Q.empty()) { pair<int,int> pi = Q.front(); Q.pop(); rep(k,4) { int x = pi.first+dx[k], y = pi.second+dy[k]; if(x > -1 && x < h && y >= 0 && y < w ) { if(input[i][j] == input[x][y] && !visited[x][y]) { visited[x][y] = true; tmp.blocks.push_back(make_pair(x,y)); Q.push(make_pair(x,y)); input[x][y] = '.'; } } } } bv.push_back(tmp); } } } rep(i,bv.size()) { rep(j, bv[i].blocks.size()) { in[bv[i].blocks[j].first][bv[i].blocks[j].second] = bv[i].num; } bv[i].getG(); } rep(i, bv.size()) { int bmin= 100,bmax = -1; rep(j, bv[i].blocks.size()) { int y = bv[i].blocks[j].first, x = bv[i].blocks[j].second; if(y > 0 && in[y-1][x] != in[y][x] && in[y-1][x] != -1) { bv[i].above.push_back(in[y-1][x]); } if(y < h-1 && (in[y+1][x] == -1 || in[y+1][x] == in[y][x])) continue; bmin = min(bmin, x); bmax = max(bmax, x); } sort(bv[i].above.begin(), bv[i].above.end()); vector<int>::iterator it = unique(bv[i].above.begin(), bv[i].above.end()); bv[i].above.erase(it, bv[i].above.end()); bv[i].bl = bmin; bv[i].br = bmax+1; } int root; rep(j,w) if(in[h-1][j] != -1) root = in[h-1][j]; calcG(root,bv); if(rec(root,bv)) cout<<"STABLE"<<endl; else cout<<"UNSTABLE"<<endl; } }