ICPC 2010 Japan Domestic Problem D ぐらぐら

問題

下のコード解説
１．ピースにユニークなラベルをつける。
２－１．ピースＡの上にピースＢがあるとき onPiece[A][B] がtrueになるような配列を作る
２－２．ついでに下のピース（地面）と接している左端と右端のピースを求めておく
３．onPiece をウォーシャルフロイドで推移閉方に拡張
４．すべてのピースに対して、そのピースに乗っているブロックの重心求めて安定かどうか調べる

ピースごとのモーメントとブロック数をラベル付けするときに求めておけば、４のなかのモーメント計算を省略できる。
もっと単純にならんかなー。

<br /><br />#include <iostream><br /><br />using namespace std;<br /><br />#define TRACE(E) {E;}<br /><br />int width, height;<br />int piece[12][62];<br />char m[12][62];<br />int pieceNum;<br /><br />bool onPiece[600][600];<br /><br />const int dx[] = {1,0,-1,0};<br />const int dy[] = {0,1,0,-1};<br /><br />void labeling( int x, int y, char ch, int label )<br />{<br /> piece[x][y] = label;<br /><br /> for( int i = 0; i < 4; ++i )<br /> {<br /> int nx = x+dx[i], ny = y+dy[i];<br /><br /> if( m[nx][ny] == ch && piece[nx][ny] == 0 )<br /> {<br /> labeling(nx,ny,ch,label);<br /> }<br /> }<br />}<br /><br />int main()<br />{<br /> while( cin >> width >> height, width|height )<br /> {<br /> memset( piece, 0, sizeof(piece) );<br /> memset( m, 0, sizeof(m) );<br /><br /> for( int y = height; y >= 1; --y )<br /> {<br /> for( int x = 1; x <= width; ++x )<br /> {<br /> cin >> m[x][y];<br /> }<br /> }<br /><br /> pieceNum = 0;<br /><br /> memset( onPiece, 0, sizeof(onPiece) );<br /><br /> int left[600], right[600];<br /><br /> for( int i = 1; i <= width*height; ++i )<br /> {<br /> left[i] = 11;<br /> right[i] = 0;<br /> }<br /><br /> for( int y = 1; y <= height; ++y )<br /> {<br /> for( int x = 1; x <= width; ++x )<br /> {<br /> if( '1' <= m[x][y] && m[x][y] <= '9' && piece[x][y] == 0 )<br /> {<br /> int label = ++pieceNum;<br /> onPiece[label][label] = true;<br /> labeling(x,y,m[x][y],label);<br /> }<br /> }<br /> }<br /><br /> for( int x = 1; x <= width; ++x )<br /> {<br /> if( piece[x][1] == 0 )<br /> {<br /> continue;<br /> }<br /><br /> left[1] = min( left[1], x );<br /> right[1] = max( right[1], x );<br /> }<br /><br /> for( int x = 1; x <= width; ++x )<br /> {<br /> for( int y = 2; y <= height; ++y )<br /> {<br /> int label = piece[x][y];<br /><br /> if( label == 0 )<br /> {<br /> continue;<br /> }<br /><br /> if( label != piece[x][y-1] && piece[x][y-1] != 0 )<br /> {<br /> onPiece[piece[x][y-1]][label] = true;<br /> left[label] = min( left[label], x );<br /> right[label] = max( right[label], x );<br /> }<br /> }<br /> }<br /><br /> for( int i = 1; i <= pieceNum; ++i )<br /> {<br /> for( int j = 1; j <= pieceNum; ++j )<br /> {<br /> if( onPiece[j][i] )<br /> {<br /> for( int k = 1; k <= pieceNum; ++k )<br /> {<br /> onPiece[j][k] |= onPiece[i][k];<br /> }<br /> }<br /> }<br /> }<br /> <br /> bool ans = true;<br /><br /> for( int pieceIndex = 1; pieceIndex <= pieceNum; ++pieceIndex )<br /> {<br /> int mx = 0;<br /> int s = 0;<br /><br /> for( int x = 1; x <= width; ++x )<br /> {<br /> for( int y = 1; y <= height; ++y )<br /> {<br /> if( onPiece[pieceIndex][piece[x][y]] )<br /> {<br /> mx += x;<br /> ++s;<br /> }<br /> }<br /> }<br /><br /> // mx/s <= left[pieceIndex]-0.5 || right[pieceIndex]+0.5 <= mx/s<br /> if( left[pieceIndex]*2*s-s >= mx*2 || mx*2 >= right[pieceIndex]*s*2+s )<br /> {<br /> ans = false;<br /> break;<br /> }<br /> }<br /> <br /> cout << ( ans ? "STABLE" : "UNSTABLE" ) << endl;<br /> }<br /><br /> return 0;<br />}<br />