迷路の最短路問題
蟻本から。
スタート、ゴール、壁、通路が'S', 'G', '#', '.'で表されている二次元配列の地図で、スタートからゴールまでの最短経路(必ず存在する)の長さを返す。
ざ・BFS。
import itertools as it def solve(map_): def neighbors(i,j): dirs = ((i+i1, j+j1) for i1, j1 in it.product((-1,0,1), repeat=2)) return ((n, m) for n, m in dirs if not n==-1 and not n==len(map_) and not m==-1 and not m==len(map_[0]) and not map_[n][m] == '#') for i, row in enumerate(map_): for j, v in enumerate(row): if v == 'S': start = (i, j) break counter = 0 next_layer = set(start) while next_layer: for i, j in next_layer: if map_[i][j] == 'G': return counter map_[i][j] == '#' counter += 1 next_layer = set(it.chain.from_iterable(neighbors(i, j) for i, j in next_layer)) return -1
neighbors
関数がどうしてもダサい。map_をdict化すればかなり綺麗になるが、競プロ的にどうなんだろう・・・
とりあえず書いてみる:
import itertools as it def solve(map_): map_dict = {(i,j):v for i, row in enumerate(map_) for j, v in enumerate(row)} start = next((i,j) for i, row in enumerate(map_) for j, v in enumerate(row) if v == 'S') def neighbors(i, j): neighbor_cells = ((i+i1, j+j1) for i1, j1 in it.product((-1,0,1), repeat=2)) return (cell for cell in neighbor_cells if map_dict.get(cell, '#') != '#') counter = 0 next_layer = set(start) while next_layer: for cell in next_layer: if map_dict[cell] == 'G': return counter map_dict[cell] == '#' counter += 1 next_layer = set(it.chain.from_iterable(neighbors(*cell) for cell in next_layer)) return -1
頭にO(n)の処理を一つ加えただけだが、実際にn回ループが回っているのでやはり少し罪悪感がある。
startの探索はgenerator expressionをnextしているのでO(n)なだけでなく必要最低限しか回らない。
neighborsが呼び出される時点で(i+0, j+0)
点は'#'になっている事実を使って明示的なチェックをサボっているのも、「現状ではいいが変更するときに危険」とソフトウエア工学的には心配になる。
あと、問題の前提条件で「必ずスタートからゴールへの経路が一つはある」と書いてあっても最後にreturn -1
って書きたくなる。