Digging a canal (Scientific Expedition) - 水路を掘る
どんな問題？
Digging a canal
http://www.checkio.org/mission/digging-a-canal/
マップの北の端から南の端に水路を掘ってつなげたい。
最短で何マスの水路を掘る必要があるかを調べよ。
水路を掘ると、陸のマスを水のマスに変更することができる。マップ北（上端）から、南（下端）へ、水のマスをつなげるためには、何マスの陸を水に変更すればいいか、という問題。
引数のマップデータは、水が0、陸が1の list of list で渡される。
戻り値は、水路を掘る最小数を返す。
- 水のマスは、縦と横でつながり、斜めにはつながらない。
- マップは、辺の長さが10未満の長方形。
例題：
checkio([[1, 1, 1, 1, 0, 1, 1], [1, 1, 1, 1, 0, 0, 1], [1, 1, 1, 1, 1, 0, 1], [1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 1, 1, 1, 1], [1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1]]) == 2 checkio([[0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 1, 0, 1, 1], [1, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0]]) == 3 checkio([[1, 1, 1, 1, 1, 0, 1, 1], [1, 0, 1, 1, 1, 0, 1, 1], [1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 1, 0, 1, 1], [0, 0, 1, 1, 0, 0, 0, 0], [1, 0, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1, 1]]) == 2
どうやって解く？
問題文に、グラフ探索と最適化の問題と書いてある。
これは、アルゴリズムの本で見た、「重み付きのグラフ」というやつだろうか？
陸地ならコスト1で移動、水ならコスト0で移動できるという条件で、最短経路を求めるというような問題なのかな？
アルゴリズムの本は図書館に返却してしまったので、とりあえずは、アルゴリズムを気にせずに自力で解いてみることにする。今度、もう一度借りてこよう。
すべてのマスについて、北側（上端）からの最短距離を調べていく。
例えば、こういうマップなら、（陸=1、水=0）
１０１１ １０１１ １１１１ １１１１
上端からの距離はこうなる。
１０１１ １０１２ ２１２３ ３２３４
この例なら、最下行に2があるので、2が最短距離だとわかる。
このように上端からの距離を求めるためには、
- 最上行の水は0、陸は1として初期化
- 0とつながっている水は、すべて0とする。
- 0に隣接する陸は、1とする。
- 最下層に達するまで繰り返し。
という流れで調べていく。
最初に、隣接するマスを取得する get_adjacent()と、すべてのマスの座標 all_pts を定義しておく。
def get_adjacent(x, y): result = [(x + pt[0], y + pt[1]) for pt in [(-1, 0), (1, 0), (0, -1), (0, 1)]] return [(x, y) for x, y in result if 0 <= x < w and 0 <= y < h] w, h = len(data[0]), len(data) all_pts = [(x, y) for y in range(h) for x in range(w)]
次に、全マス分のフラグを作る。フラグはNoneで初期化しておき、上端からの距離がわかれば、それを入力していく。
最上行の水は0、陸は1として初期化するので、data[0]をそのまま使う。残りはNoneにしておく。
flags = [data[0]] + [[None for x in range(w)] for y in range(h - 1)]
「Xとつながっている水マスは、すべてXとなる」という部分は、スタックを使った。
# フラグがstepのマスをスタックに入れる stack = [(x, y) for x, y in all_pts if flags[y][x] == step] while stack: x, y = stack.pop() for ax, ay in get_adjacent(x, y): # 隣接マスを調べて if flags[ay][ax] is None and data[ay][ax] == 0: # 未探索の水マスであれば flags[ay][ax] = step # フラグをstepにして stack.append((ax, ay)) # スタックに追加
「Xに隣接する陸地は、X+1となる」という部分は、単純にforループで処理。
# フラグがstepのマスをリストにする pts = [(x, y) for x, y in all_pts if flags[y][x] == step] for pt in pts: for ax, ay in get_adjacent(*pt): # 隣接マスを調べて if flags[ay][ax] is None and data[ay][ax] == 1: # 未探索の陸地であれば flags[ay][ax] = step + 1 # フラグをstep+1にする
まとめ
ADJACENT = {(-1, 0), (1, 0), (0, -1), (0, 1)}
def checkio(data):
def get_adjacent(x, y):
# 上下左右のマスを取得（範囲チェックあり）
result = [(x + pt[0], y + pt[1]) for pt in ADJACENT]
return [(x, y) for x, y in result if 0 <= x < w and 0 <= y < h]
w, h = len(data[0]), len(data)
all_pts = [(x, y) for y in range(h) for x in range(w)]
flags = [data[0]] + [[None for x in range(w)] for y in range(h - 1)] # 最上行は陸1、海0、残りはNone
for step in range(h):
# stepに接する海のつながりをすべてstepにする
stack = [(x, y) for x, y in all_pts if flags[y][x] == step]
while stack:
x, y = stack.pop()
for ax, ay in get_adjacent(x, y):
if flags[ay][ax] is None and data[ay][ax] == 0:
flags[ay][ax] = step
stack.append((ax, ay))
# stepに隣接する陸をstep+1にする
pts = [(x, y) for x, y in all_pts if flags[y][x] == step]
for pt in pts:
for ax, ay in get_adjacent(*pt):
if flags[ay][ax] is None and data[ay][ax] == 1:
flags[ay][ax] = step + 1
# 最下層に到達したら終了
if any(f == step for f in flags[-1]):
return step
return h
http://www.checkio.org/mission/digging-a-canal/publications/natsuki/python-3/first/
いちおうクリアしたが、アルゴリズムの本を見て、正統派のやりかたで解いてみたい。
後日、続きを書くことにしよう。（最近こればっかり）
そして書き忘れていたが、これがScientific Expeditionの最後の問題となる。確かもう1問あったはずだが、いつの間にか消えていた。まあいいや。
次は、前から気になってる Alice In Wonderland でも行こうかな？
