AOJ-ICPC 200点: 迷図と命ず(Amazing Mazes)

幅優先探索ですね。

lines[y][x]は左上(番兵含め)を(0, 0)として、[ (x, y)の四角の右側に壁があるか, 下側に壁があるか ] という形です。少し入力の処理に手間がかかりました。番兵の使い方がわかってきたぞ

探索のキューをuniqするのを忘れてて、MLEを何度か出してしまいました…
uniqしなくても、探索の前に「訪問済みであれば飛ばす」という処理を入れればうまく動きます。

loop do
  w, h = gets.split.map(&:to_i)
  break if w == 0
  lines = [[[false, true]] * (w+1)] # 番兵
  (2 * h - 1).times do |i|
    y = i / 2 + 1
    if i % 2 == 0
      lines[y] = [[true, false]] # 壁があればtrue
      gets.split.map(&:to_i).each do |ch|
        lines[y] << [false, false] if ch == 0
        lines[y] << [true, false]  if ch == 1
      end
      lines[y] << [true, false] # 右端(番兵)
    else
      gets.split.map(&:to_i).each.with_index(1) do |ch, ci|
        lines[y][ci][1] = true if ch == 1
      end
    end
  end
  lines[-1].each do |c|
    c[1] = true # 一番下の行のマス全てに、下側に壁があるとする
  end

  d = []
  queue = [[1, 1]]
  d[1] = []
  d[1][1] = 0
  visited = []
  while queue.size > 0
    cx, cy = queue.shift
    visited[cy] ||= []
    visited[cy][cx] = true # 訪問済み
    break if cx == w && cy == h

    if !lines[cy-1][cx][1] && !(visited[cy-1] && visited[cy-1][cx]) # 上
      queue << [cx, cy-1]
      d[cy-1] ||= []
      d[cy-1][cx] = d[cy][cx] + 1
    end
    if !lines[cy][cx][1] && !(visited[cy+1] && visited[cy+1][cx]) # 下
      queue << [cx, cy+1]
      d[cy+1] ||= []
      d[cy+1][cx] = d[cy][cx] + 1
    end
    if !lines[cy][cx][0] && !(visited[cy] && visited[cy][cx+1]) # 右
      queue << [cx+1, cy]
      d[cy][cx+1] = d[cy][cx] + 1
    end
    if !lines[cy][cx-1][0] && !(visited[cy] && visited[cy][cx-1]) # 左
      queue << [cx-1, cy]
      d[cy][cx-1] = d[cy][cx] + 1
    end

    queue.uniq!
  end

  puts (d[h] && d[h][w]) ? (d[h][w] + 1) : 0
end