RubyでACM/ICPC vol. 1

引き続き，2004愛媛大会のproblem BをRubyで解いてみました。
プログラムを見れば自明ですが，以下のような方針を再帰で実装しました。

1. '@'の上下左右の黒タイルを'c'（checked）でマークする。
2. マップから'c'タイルを探し，見つからなければ3へ進む。
　i. 見つかった'c'タイルを'd'（done）でマークする。
　ii. 'd'でマークしたタイルの上下左右の黒タイルを'c'でマークする。
　iii. 2に戻る。
3. 'c'でマークしたタイルの数に'@'マークの分の1を加えて出力。

とりあえず，以下のようになりました。

def scan_map(x, y, map, n)
  return n if x == nil || y == nil
  n += mark(x, y, map) 

  i, j = get_not_centered(map)
  scan_map(i, j, map, n)
end

def mark(x, y, map)
  map[y][x] = "d"
  arr = [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]
  xlim = map[0].size - 1
  ylim = map.size - 1

  arr.delete_if{|p|
    p[0] < 0 || p[1] < 0 || p[0] > ylim || p[1] > xlim
  }

  count = 0
  arr.each{|p|
    i, j = p[0], p[1]
    if map[i][j] == "."
      map[i][j] = "c"
      count += 1
    end
  }
  return count
end

def get_not_centered(map)
  map.each_with_index{|line, j|
    line.each_with_index{|val, i|
      return i, j if val == "c"
    }
  }
  return nil, nil
end

while line = gets
  line =~ /(\d+) (\d+)/
  w, h = $1.to_i, $2.to_i
  exit if h == 0

  map = []
  x, y = 0, 0
  h.times{|i|
    line = gets
    map[i] = line.chomp!.split(//)
    y, x = i, map[i].index("@") if map[i].include?("@")
  }
  p scan_map(x, y, map, 0) + 1   #add '@' cell
end

パターンマッチは1回だけだから目をつぶるとしても，馬鹿正直に'c'タイルを探しているget_not_centered(map)メソッドは効率がよくありません。
(1, 2)のタイルをarr[12]で表すなどすれば1つの配列でmapを表現してみると