Codeforces #191 Div2 D "Block Tower"
問題
http://codeforces.com/contest/327/problem/D
訳
紙を使ったゲームは飽きたため(問題Aのことね)ラハブはコンピューターゲームをすることにした。彼がプレイしているゲームは"Block Towers"と呼ばれている。これはn行m列のマス目を使ったゲームである。このゲームの目的は、いくつかのタワーを建てて自分の町を築き上げる事である。いくつかのマスには大きな穴が開いており、そこにはタワーを作る事ができない。その他のマスは空きマスである。空きマスに対し、ラハブは以下の2つのタイプの内、1つのタワーを作る事が出来る。
1. ブルータワー。これは人口が最大100人となっている。 2. レッドタワー。これは人口が最大200人となっている。 ただし、このタワーを作るときは、隣り合うマスに少なくとも1つ、 ブルータワーが建っていなければならない。 辺を共有している2つのマスが、隣り合っているマスとなる。
ラハブは任意のタワーを壊す事も出来る。この行動は、好きなだけ行う事が出来る。タワーが壊される時、他のタワーは影響を受けず、そのマスは空きマスとなる(よって、ラハブが望めば、再び同じマスにタワーを建てることができる)。
人口を最大限にするための最善の行動を出力せよ。
制約(入力)
1 <= n, m <= 500
制約(出力)
行動は10^6まで行える
考えた事
こんな感じのフィールドだったとして、
隣り合っているマス同士のかたまりの1つに着目する。
とりあえず青いタワーで埋め尽くし、
壊しては
赤いタワーを建て、
壊しては
赤いタワーを建て、
最終的に1つの青いタワー以外は全部赤いタワーにすることができる。(これが最善)
行動も出力しなくてはならないので、
BFSでかたまりを探索していって
根付き木を作り、
行き際に青いタワーを、帰り際に壊して赤いタワーをDFSで作っていけばおk
ソースコード
int W, H; vector< string > field; bool chk[510][510]; vector< pair<int, int> > G[510][510]; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; // 根付き木を作る void make_G( int sx, int sy ){ queue< pair<int, int> > que; que.push(make_pair( sx, sy )); chk[sx][sy] = true; int cnt = 0; while( !que.empty() ){ int x = que.front().first; int y = que.front().second; que.pop(); for( int d = 0; d < 4; d++ ){ int tx = x + dx[d]; int ty = y + dy[d]; if( tx < 0 || W <= tx || ty < 0 || H <= ty ) continue; if( chk[tx][ty] || field[ty][tx] == '#' ) continue; chk[tx][ty] = true; G[x][y].push_back(make_pair(tx, ty)); G[tx][ty].push_back(make_pair(x, y)); que.push( make_pair(tx, ty) ); } } } class S{ public: S( char _op, int _x, int _y ): op(_op),x(_x),y(_y){} void print(){ printf( "%c %d %d\n", op, y+1, x+1 ); } char op; int x, y; }; queue<S> ops; // タワーを作り、行動を記録していく void create_Tower( int px, int py, int x, int y ){ // create blue ops.push(S('B', x, y)); // child for( int i = 0; i < G[x][y].size(); i++ ){ int cx = G[x][y][i].first; int cy = G[x][y][i].second; if( px == cx && py == cy ) continue; create_Tower( x, y, cx, cy ); } if( px != -1 ){ // destroy blue ops.push(S('D', x, y)); // create red ops.push(S('R', x, y)); } } int main() { // 入力 cin >> H >> W; for( int i = 0; i < H; i++ ){ string line; cin >> line; field.push_back( line ); } memset( chk, false, sizeof(chk) ); for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( field[y][x] == '#' || chk[x][y] ) continue; // 根付き木を作る make_G( x, y ); // タワーを作り、行動を記録していく create_Tower( -1, -1, x, y ); } } // 出力 cout << ops.size() << endl; while( !ops.empty() ){ ops.front().print(); ops.pop(); } }