迷路問題解いてみた

http://d.hatena.ne.jp/hajimehoshi/20100113/1263316177
って書いてたのでリンク先の問題文だけ読んで、なんとなくrubyで解いてみた。
4時から始めて5時13分という結果でした。

どうやってとこうかなーって思って悩んだ結果、それぞれのマスを、最寄の数字+1と全て演算していくのを繰り返していけばいいやと
考えついて、求めてみたあとに、そういえば、ゴールから線引くのどうしよう。これだと何歩で歩けるって結果にならね！？
って思って後から逆順に遡るロジックを付け足しました。
なので、set_addressメソッドに、そのマスの値を更新するかどうかのオプションを追加してたりしてますね。後付で。

今改めて、http://d.hatena.ne.jp/hajimehoshi/20100113/1263316177を読んでみると、中心となる解き方は一緒の方法
使ってる…。
まるでカンニングしたみたいだ……。
一応、解き方とか読まずに、元となるアルゴリズムとか全然知識無しで自力で考えたつもりなんですが……、
説得力皆無！！

とりあえずだらだらと書いた、リファクタリングもしてないソースコードを貼っていきますね。
われながら数字用の@mapと、後付で大急ぎでつけた@str_mapとか、変数名ひどいと思います。

START = 0
CANT_GO = -1
CAN_GO = -2
GOAL = -3
X = 1
Y = 0

def get_cell(address) 
  return @map[address[X]][address[Y]]
end

def addition_address(address, diff) 
  return [address[Y] + diff[Y], address[X] + diff[X]]
end

def set_address(address, update_flg = true)
  min = nil
  min_diff = nil
  [[-1, 0], [0, -1], [1, 0], [0, 1]].each do | diff |
    get_value = get_cell(addition_address(address, diff))
    if get_value >= START && ( min.nil? || min > get_value )
      min = get_value
      min_diff = diff 
    end
  end
  if min && update_flg
    @map[address[X]][address[Y]] = min + 1
  end
  return min_diff
end

start_address = []
goal_address = []

@map = []
@str_map = []

#map展開
open("input.txt").each do |str|
  row = []
  str.split(//).each do | cell | 
    case cell
    when " " 
      row << CAN_GO
    when "S" 
      start_address = [row.size, @map.size]
      row << START
    when "G"
      goal_address = [row.size, @map.size]
      row << GOAL
    when "*"
      row << CANT_GO
    end
  end
  @map << row
  @str_map << str.split(//)
end

p @map

y_max = @map.size
x_max = @map[0].size
while get_cell(goal_address) == GOAL
  y_max.times do | y | 
    x_max.times do | x | 
      if get_cell([x, y]) < CANT_GO
        set_address([x, y])
      end
    end
  end
  p @map
end
current_address = goal_address
while current_address != start_address
  diff = set_address(current_address, false) 
  current_address = addition_address(current_address, diff)
  @str_map[current_address[X]][current_address[Y]] = '$' if current_address != start_address
end
puts @str_map.map{|cols| cols.join}.join