WARush

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

SRM625 Div1 Medium "BlockTheBlockPuzzle"

問題

TopCoder Statistics - Problem Statement

"Block Puzzle"はn * nのマスでできたボード上で遊ぶゲームである。いくつかのマスはスタートマスとなっており、1つのマスがゴールマスとなっている。

プレイヤーはまず始めに1つのスタートマスを選び、そこに1x1x2のブロックを1x1の面を選んだマスと接するようにして置く。ゲームの目的はブロックをゴールマスへ移動させることである。(その際に、1x1の面がゴールマスと接するようにする)このゲームはブロックを転がしてボード上を移動させる。転がし方には次のような制限がある。1x1の面で立っている状態からは任意の4方向に転がすことができる。しかし、2x1の面で寝ている状態から転がすときは、1x1の面で立っている状態にしなければならない。

この説明を図にしたものが以下である。(色が薄い方は転がす前であり、濃いほうは転がした後である。)
f:id:Ekaing:20140622001611p:plain

これまでのところ、このゲームは単純である。しかし、いくつかのマスには穴が空いており、それが子のゲームを難しくしている。ブロックが接しているマス全てが穴であった場合、ブロックは落ち、ゲームオーバーとなる。ボードの端を越えた場合もブロックは落ちてしまう。(ブロックが2x1の面にて立っていて、接している2つのマスの内1つだけが穴、もしくはボードの外だった場合、ブロックは落ちずにゲームオーバーとならない。ブロックの半分がボードに引っかかり落ちないようになっている。)

ボーンは"Block Puzzle"をやり込んでいた。ジュルスは退屈しのぎにボーンのゲームでゴールに到達できないよう、新しく穴を開けようとしていた。ジュルスはスタートマスでもゴールマスでもないマスのみ穴を開けることができる。彼はなるべく穴を開ける数をなるべく少なくしたいと思っていた。

あなたは現在のボードの状態がString配列のboardとして与えられる。'.'の文字は普通のマス、'H'の文字は穴マス。'b'の文字はスタートマス、'$'の文字はゴールマスを表している。ボーンがゴールできないように穴を開けたときに、その最小の穴あけ回数を返せ。もしできないようであれば-1を返せ。

制約

3 <= n <= 50


考えたこと

動かし方の制限から1x1で立っている状態から再び1x1で状態で移動するときは、上下左右3マス離れたマスにしかいけない。なので、ゴールマスから3マスずつ離れたマスが、考える対象のマスとなる。

例えば、Sample3は次のようになっている

b..$...
...H...
.......
b..b..b
...H...
.......
b..b..b

ここから、ゴールマスに関連するマスのみを抜き出すと以下のようになる。
f:id:Ekaing:20140622005228j:plain

2つの頂点間を移動できないようにするためには、2つとも穴にしてしまえばよいので、移動できなくするためのコストは以下のようになる。
f:id:Ekaing:20140622005334j:plain

ここで、全てのスタートマスからゴールマスへ到達できないようにするためには、以下のようなカットが必要となる。
f:id:Ekaing:20140622005419j:plain

これで、この問題は最小カット問題かなあ?とイメージできる。

問題は、頂点がスタートマスまたはゴールマスでない普通のマスの場合、その頂点自体に穴を掘れてしまうことである。これは、普通マスの頂点を2つに分離し、入次用と出次用で分けて、その間をコスト1としてあげるとよい。イメージは以下の通り
f:id:Ekaing:20140622005652j:plain

ソースとシンクは以下のように張る
f:id:Ekaing:20140622010731j:plain

これで最大流=最小カットを解けばそれが答えとなる。


ソースコード

// 最大流クラス(実装は割愛)
class MaxFlow {
public:
    MaxFlow(int vertexNumber);
    ~MaxFlow();
    void addEdge(int v, int u, int cap);
    int flow(int s, int t);
};

const int INF = 10000;

class BlockTheBlockPuzzle {
public:

    int minimumHoles(vector <string> board) {
        int n = board.size();

        MaxFlow mf(n * n * 2 + 1);
        
        int Sid = n * n * 2; // ソース用頂点id
        int Tid = -1;        // シンク用頂点id

        int dx[4] = {0, 0, -1, 1};
        int dy[4] = { -1, 1, 0, 0 };
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                int sid = y * n + x;
                char src = board[y][x];
                if (src == 'b') {
                    // スタートマスであれば、
                    // ソースからエッジを張る
                    mf.addEdge(Sid, sid, INF);
                }
                if (src == 'H') {
                    // 穴であればやらない
                    continue;
                }
                if (src == '.') {
                    // 普通マスであれば頂点を2つにし、
                    // その間をコスト1とする
                    int sid2 = sid + n * n;
                    mf.addEdge(sid, sid2, 1);
                    mf.addEdge(sid2, sid, 1);
                }
                if (src == '$') {
                    // ゴールマスであれば、idを保持
                    Tid = sid;
                }
                for (int d = 0; d < 4; d++) {
                    int ny = y + dy[d] * 3;
                    int nx = x + dx[d] * 3;
                    if (nx < 0 || n <= nx || ny < 0 || n <= ny) continue;
                    char dst = board[ny][nx];
                    int did = ny * n + nx;
                    if (dst == 'H') {
                        // 対向が穴であれば何もしない
                        continue;
                    }
                    if (dst == '.') {
                        // 対向が普通マスであれば、
                        // 入次用のidに対してエッジを張るようにする
                        did += n * n;
                    }

                    // コスト計算
                    int cs = 0, ch = 0;
                    char c1 = board[y + dy[d] * 1][x + dx[d] * 1];
                    char c2 = board[y + dy[d] * 2][x + dx[d] * 2];
                    if (c1 == 'b') cs++;
                    if (c1 == 'H') ch++;
                    if (c2 == 'b') cs++;
                    if (c2 == 'H') ch++;
                    int cost = 2 - ch;
                    if (cs != 0) cost = INF; // スタートマスであれば穴掘り不可

                    // 対向へエッジを張る
                    mf.addEdge(sid, did, cost);
                }
            }
        }

        // 最小カット
        int minCat = mf.flow(Sid, Tid);

        // INFを超えていたら-1
        if (minCat >= INF) return -1;
        return minCat;
    }
};