迷路の最短路問題

蟻本から。

スタート、ゴール、壁、通路が'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って書きたくなる。