WARush

SRMの結果とか、解けた問題のコードを書いていきます

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まで行える


考えた事

こんな感じのフィールドだったとして、
f:id:Ekaing:20130721224808j:plain
隣り合っているマス同士のかたまりの1つに着目する。
f:id:Ekaing:20130721224816j:plain
とりあえず青いタワーで埋め尽くし、
f:id:Ekaing:20130721224825j:plain
壊しては
f:id:Ekaing:20130721224834j:plain
赤いタワーを建て、
f:id:Ekaing:20130721224843j:plain
壊しては
f:id:Ekaing:20130721224847j:plain
赤いタワーを建て、
f:id:Ekaing:20130721224900j:plain
最終的に1つの青いタワー以外は全部赤いタワーにすることができる。(これが最善)
f:id:Ekaing:20130721224907j:plain

行動も出力しなくてはならないので、
f:id:Ekaing:20130721224921j:plain
BFSでかたまりを探索していって
f:id:Ekaing:20130721224955j:plain
根付き木を作り、
f:id:Ekaing:20130721225002j:plain
行き際に青いタワーを、帰り際に壊して赤いタワーをDFSで作っていけばおk
f:id:Ekaing:20130721225010j:plain


ソースコード

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();
    }
}