SRM625 Div1 Medium "BlockTheBlockPuzzle"
問題
TopCoder Statistics - Problem Statement
訳
"Block Puzzle"はn * nのマスでできたボード上で遊ぶゲームである。いくつかのマスはスタートマスとなっており、1つのマスがゴールマスとなっている。
プレイヤーはまず始めに1つのスタートマスを選び、そこに1x1x2のブロックを1x1の面を選んだマスと接するようにして置く。ゲームの目的はブロックをゴールマスへ移動させることである。(その際に、1x1の面がゴールマスと接するようにする)このゲームはブロックを転がしてボード上を移動させる。転がし方には次のような制限がある。1x1の面で立っている状態からは任意の4方向に転がすことができる。しかし、2x1の面で寝ている状態から転がすときは、1x1の面で立っている状態にしなければならない。
この説明を図にしたものが以下である。(色が薄い方は転がす前であり、濃いほうは転がした後である。)
これまでのところ、このゲームは単純である。しかし、いくつかのマスには穴が空いており、それが子のゲームを難しくしている。ブロックが接しているマス全てが穴であった場合、ブロックは落ち、ゲームオーバーとなる。ボードの端を越えた場合もブロックは落ちてしまう。(ブロックが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
ここから、ゴールマスに関連するマスのみを抜き出すと以下のようになる。
2つの頂点間を移動できないようにするためには、2つとも穴にしてしまえばよいので、移動できなくするためのコストは以下のようになる。
ここで、全てのスタートマスからゴールマスへ到達できないようにするためには、以下のようなカットが必要となる。
これで、この問題は最小カット問題かなあ?とイメージできる。
問題は、頂点がスタートマスまたはゴールマスでない普通のマスの場合、その頂点自体に穴を掘れてしまうことである。これは、普通マスの頂点を2つに分離し、入次用と出次用で分けて、その間をコスト1としてあげるとよい。イメージは以下の通り
ソースとシンクは以下のように張る
これで最大流=最小カットを解けばそれが答えとなる。
ソースコード
// 最大流クラス(実装は割愛) 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; } };