ABC 400 D問題 Takahashi the Wall Breaker
D 問題には歯が立たないと思っていましたが、コンテスト後に時間をかけることで ABC 400 の D 問題を塗りつぶしアルゴリズムを使って回答することが出来ました。
問題は A から順番に難易度が上がりますが、C 問題より D 問題のほうが解けそうな気がしたのでコンテスト終了後にチャレンジしてみました。
問題
ABC 400のD - Takahashi the Wall Breaker
壁と通路で構成された二次元マップが与えられて、現在位置から目的地に向かう問題。ただし、目的地までの間に壁があり、キックで壁を壊すことが可能1で、このキックの最小回数を求める問題。
方法
スタート地点から行ける範囲を制限する壁を全て壊して、目的地が行ける範囲に含まれるようになれば良いと考えました。そのためには制限している壁を見つける必要があります。
この壁を見つける方法として、2 つの方法が浮かびました。
- ペイントソフトの塗りつぶしと同じアルゴリズムで行ける範囲を全て訪問し、壁に隣接していたら壁を壊す。
- 純粋に行ける範囲を全て訪問するとメモリーと計算時間の制限に引っかかる可能性があります。そこで訪問する場所を制限するため、まずスタート地点から上下左右に各一方向に探索して壁に隣接する場所を見つける。そのうえで壁を壊しながら壁伝いに次の候補地を訪問する。
最初は 2 の方法を取ろうとしたのですが、4 方向全てに壁の島があった場合にキック回数が無駄に増えてしまうことに気が付きました。
そこで 1 の単純な塗りつぶしアルゴリズムを採用しました。スタート地点から順番に隣の場所を訪問し、訪問できる場所が無くなったら 1 ラウンド終了。壁を取り払って、更に次の区画を訪問していく。この過程で目的地を訪問したら、そこで終了とします。
壁を壊すタイミングですが、訪問しながら壁を壊してしまうと同じ壁に隣接する場所を訪問した時の処理が難しくなるので、単純に壊す壁を覚えておいてラウンド終了後にまとめて壊すことにしました。
技術的工夫
- 破壊予定の壁を記録しておく方法ですが、同じ壁を何度も破壊予定リストに入れることになります。そこで破壊予定の壁の場所を表す tuple は、List 型ではなく自動的に重複を取り除く Set 型に入れておくことにしました。
- 目的地を訪問した時に二重ループから抜ける必要があります。最初はループを抜ける度に目的地を訪問したか調べていましたが、break しなかった時に実行される
elseの性質を使うことにしました。break しなかったときにはelseブロックが実行されるので、continueで次のループにジャンプします2。break したときには、elseブロックが飛ばされて再度 break が実行されるようにしました。
h, w = map(int, input().split())
map_data = list()
visited = list()
for _ in range(h):
row = input()
map_data.append([row[i] for i in range(w)])
visited.append([False] * w) # visited.append([False for _ in range(w)])
a, b, c, d = [int(v) for v in input().split()]
trow, tcol, frow, fcol = a - 1, b - 1, c - 1, d - 1 # adjust for 0-start
# use Set instead of List because same points may be pushed for multiple times.
next_stack = set()
stack = set()
next_stack.add((trow, tcol))
step = 0
while len(next_stack) > 0:
stack = next_stack
next_stack = set()
kicked = set()
while len(stack) > 0:
row, col = stack.pop()
if visited[row][col]:
continue
visited[row][col] = True
map_data[row][col] = str(step) # for debug
# if visited[frow][fcol]:
if row == frow and col == fcol:
# arrived at the fish market
break
for delta in [(-1, 0), (0, -1), (1, 0), (0, 1),]:
y = row + delta[0]
x = col + delta[1]
if (w > x >= 0 and h > y >= 0) and not visited[y][x]:
if map_data[y][x] == '#':
# visit at the next round
next_stack.add((y, x))
kicked.add((y, x))
# kick one more wall on the same direction
_y = y + delta[0]
_x = x + delta[1]
if (w > _x >= 0 and h > _y >= 0) and map_data[_y][_x] == '#':
# omit adding on the next_stack because the second kicked wall should visited through the first one
kicked.add((_y, _x))
else:
stack.add((y, x))
else:
# no break or not reached the fish
# remove broken walls
step += 1
for pos in kicked:
row, col = pos
map_data[row][col] = str(step)
# for i, row in enumerate(map_data):
# print("".join(row))
# # print(visited[i])
# print("-----")
continue
# for i, row in enumerate(map_data):
# print("".join(row))
# # print(visited[i])
# print("-----")
# breaked
break
print(step)感想
コンテストの問題は A から B, C と難しくなっていきますが、C の問題くらいまでしか回答できないと思っていました。しかし、今回 C 問題は回答できませんが、D 問題をコンテスト終了後に時間をかけてとはいえ回答できたことは「やったね！」という感じです。
またこの問題の解説を読むと重み付き有向グラフとして考えるとありましたが、この問題がクラフ問題として回答できるとは考えてもみませんでした。