PKU 1027 The Same Game
懐かしい。
C++だとTLE、G++で900MS。通ったから良しとしよう……。
#include <iostream> using namespace std; const int W = 15; const int H = 10; void cluster( char b[W][H], int c[W][H] ); void fall( char b[W][H] ); int main() { int n; cin >> n; for ( int i=1; i<=n; i++ ) { char b[W][H]; for ( int y=H-1; y>=0; y-- ) for ( int x=0; x<W; x++ ) cin >> b[x][y]; cout << "Game " << i << ":" << endl; cout << endl; int remain = W * H; int score = 0; for ( int j=1; remain>0; j++ ) { int c[W][H]; cluster( b, c ); int num[W*H] = { 0 }; // 各クラスタの玉数 for ( int x=0; x<W; x++ ) for ( int y=0; y<H; y++ ) if ( c[x][y] >= 0 ) num[c[x][y]]++; int m = 0; // 最も大きいクラスタの玉数 int mx, my; // もっとも大きいクラスタの左下の玉 for ( int x=0; x<W; x++ ) for ( int y=0; y<H; y++ ) if ( c[x][y] >= 0 && num[c[x][y]] > m ) m = num[c[x][y]], mx = x, my = y; if ( m <= 1 ) break; // 玉を消す char color = b[mx][my]; for ( int x=0; x<W; x++ ) for ( int y=0; y<H; y++ ) if ( c[x][y] == c[mx][my] ) b[x][y] = ' '; remain -= m; int point = (m-2)*(m-2); score += point; fall( b ); // 表示 cout << "Move " << j << " at (" << my+1 << "," << mx+1 << "): " << "removed " << m << " balls" << " of color " << color << ", " << "got " << point << " points." << endl; } if ( remain == 0 ) score += 1000; cout << "Final score: " << score << ", " << "with " << remain << " balls remaining." << endl; if ( i < n ) cout << endl; } return 0; } // bをクラスタに分ける void cluster( char b[W][H], int c[W][H] ) { for ( int x=0; x<W; x++ ) for ( int y=0; y<H; y++ ) c[x][y] = -1; bool f[W][H] = { { false } }; for ( int i=0; ; i++ ) { // クラスタ分けされていない玉を探す for ( int x=0; x<W; x++ ) for ( int y=0; y<H; y++ ) if ( b[x][y] != ' ' && c[x][y] == -1 ) { c[x][y] = i; f[x][y] = true; goto found; } break; found:; // 隣接している玉をクラスタに分ける bool update; do { update = false; for ( int x=0; x<W; x++ ) for ( int y=0; y<H; y++ ) if ( f[x][y] ) for ( int d=0; d<4; d++ ) { int tx = x; int ty = y; switch ( d ) { case 0: tx++; break; case 1: ty++; break; case 2: tx--; break; case 3: ty--; break; } if ( 0 <= tx && tx < W && 0 <= ty && ty < H && b[tx][ty] == b[x][y] && c[tx][ty] == -1 ) { c[tx][ty] = i; f[tx][ty] = true; update = true; } f[x][y] = false; } } while ( update ); } } // 玉を詰める void fall( char b[W][H] ) { // 縦方向 for ( int x=0; x<W; x++ ) for ( int y=0; y<H-1; y++ ) if ( b[x][y] == ' ' ) { int t; for ( t=y+1; t<H-1 && b[x][t]==' '; t++ ) ; b[x][y] = b[x][t]; b[x][t] = ' '; if ( t == H-1 ) break; } // 横方向 for ( int x=0; x<W-1; x++ ) if ( b[x][0] == ' ' ) { int t; for ( t=x+1; t<W-1 && b[t][0]==' '; t++ ) ; for ( int y=0; y<H; y++ ) b[x][y] = b[t][y], b[t][y] = ' '; if ( t == W-1 ) break; } }