「はてなブックマーク - 人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか」の「startから距離で塗りつぶして、あとはgoalから距離が減る方向に辿る(koizuka)」を参考に解いてみました。
maze_string = "**************************\n" + "*S* * *\n" + "* * * * ************* *\n" + "* * * ************ *\n" + "* * *\n" + "************** ***********\n" + "* *\n" + "** ***********************\n" + "* * G *\n" + "* * *********** * *\n" + "* * ******* * *\n" + "* * *\n" + "**************************\n" class String def chr_array array = [] self.each_byte{|c| array.push(c.chr)} array end end class Maze def initialize(maze_string) @array = maze_string.split("\n").map{|line| line.chr_array} # 配列に変換 @st_goal = start_goal_postion @array[@st_goal["start"]["y"]][@st_goal["start"]["x"]] = 0 @max_y = @array.size - 1 @max_x = @array[0].size - 1 end # スタート、ゴールの座標取得 def start_goal_postion y = 0 start = goal = nil @array.each do |line| x = 0 line.each do |p| start = {"x" => x, "y" => y} if p=="S" goal = {"x" => x, "y" => y} if p=="G" x += 1 end y += 1 end {"start" => start, "goal" => goal} end def start; @st_goal["start"] end def goal; @st_goal["goal"] end def mark mark_(start["y"]-1,start["x"]) mark_(start["y"]+1,start["x"]) mark_(start["y"], start["x"]-1) mark_(start["y"], start["x"]+1) end # 再帰的にスタートからの距離を記入 def mark_(y,x) if in_frame?(y,x) && (@array[y][x]==" " || @array[y][x].is_a?(Fixnum)) # 数字のときは元の数字より小さいときは入れ替え if @array[y][x].is_a?(Fixnum) if @array[y][x] > minimum_from4points(y,x) @array[y][x] = minimum_from4points(y,x) else return end else @array[y][x] = minimum_from4points(y,x) end # このコメントをはずすと数値を書き込んでいる様子が見える。 # show; sleep(0.5) mark_(y-1,x) mark_(y+1,x) mark_(y,x-1) mark_(y,x+1) end end # 上下左右4点から最小の数字を選択し、それに1を加えた数字を取得 def minimum_from4points(y,x) if @array[y][x]!="*" work = [] work.push(@array[y-1][x]) if number?(y-1,x) work.push(@array[y+1][x]) if number?(y+1,x) work.push(@array[y][x-1]) if number?(y,x-1) work.push(@array[y][x+1]) if number?(y,x+1) minimum = work.sort.first minimum.is_a?(Fixnum) ? minimum + 1 : @array[y][x] else "*" end end # 数字かどうか判定 def number?(y,x) if in_frame?(y,x) @array[y][x].is_a?(Fixnum) else false end end # 座標の枠内判定 def in_frame?(y,x); y >= 0 && y <= @max_y && x >= 0 && x <= @max_x end # ゴールから、上下左右4点最小の座標を取得、"$"を書いてスタートまで再帰。 def write_route; write_route_(goal["y"],goal["x"]) end def write_route_(y,x) if @array[y][x]==0 @array[y][x]="S" else @array[y][x]="$" unless @array[y][x]=="G" work = [] work.push([y-1,x]) if number?(y-1,x) work.push([y+1,x]) if number?(y+1,x) work.push([y,x-1]) if number?(y,x-1) work.push([y,x+1]) if number?(y,x+1) minimum = work.sort{|a, b| @array[a[0]][a[1]] <=> @array[b[0]][b[1]]}.first # このコメントをはずすと答えのルートを書き込んでいる様子が見える。 # show; sleep(0.5) write_route_(minimum[0],minimum[1]) end end def del_num @array = @array.map do |line| line.map{|c| c.is_a?(Fixnum)?" ":c} end end def show @array.each do |line| puts line.map{|c| sprintf("%2s ",c.to_s)}.join end end end m = Maze.new(maze_string) m.mark m.show =begin スタートからの距離を書き込む。 * * * * * * * * * * * * * * * * * * * * * * * * * * * 0 * 8 * 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 * * 1 * 7 * 9 10 * 14 15 * * * * * * * * * * * * * 29 30 * * 2 * 6 7 8 * 16 15 16 17 * * * * * * * * * * * * 30 31 * * 3 4 5 6 * 18 17 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 * * * * * * * * * * * * * * * 23 * * * * * * * * * * * * 37 36 35 34 33 32 31 30 29 28 27 26 25 24 25 26 27 28 29 30 31 32 33 34 * * * 37 * * * * * * * * * * * * * * * * * * * * * * * * 39 38 39 40 41 42 * 46 47 48 49 50 51 52 53 54 55 56 57 58 59 G 65 66 * * 40 39 * 41 42 43 44 45 46 * * * * * * * * * * * 60 * 64 65 * * 41 40 41 42 * 44 45 46 47 48 49 50 51 * * * * * * * 61 * 63 64 * * 42 41 42 43 44 45 46 * 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 * * * * * * * * * * * * * * * * * * * * * * * * * * * =end m.write_route m.show =begin ゴールから小さい数字をたどる。 * * * * * * * * * * * * * * * * * * * * * * * * * * * S * 8 * 10 $ $ $ $ 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 * * $ * 7 * $ $ * 14 $ * * * * * * * * * * * * * 29 30 * * $ * 6 $ $ * 16 15 $ $ * * * * * * * * * * * * 30 31 * * $ $ $ $ * 18 17 16 17 $ $ $ $ $ 23 24 25 26 27 28 29 30 31 32 * * * * * * * * * * * * * * * $ * * * * * * * * * * * * 37 $ $ $ $ $ $ $ $ $ $ $ $ $ 25 26 27 28 29 30 31 32 33 34 * * * $ * * * * * * * * * * * * * * * * * * * * * * * * 39 $ $ $ $ $ * 46 $ $ $ $ $ $ $ $ $ $ $ $ $ G 65 66 * * 40 39 * 41 42 $ $ $ $ * * * * * * * * * * * 60 * 64 65 * * 41 40 41 42 * 44 45 46 47 48 49 50 51 * * * * * * * 61 * 63 64 * * 42 41 42 43 44 45 46 * 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 * * * * * * * * * * * * * * * * * * * * * * * * * * * =end m.del_num m.show =begin * * * * * * * * * * * * * * * * * * * * * * * * * * * S * * $ $ $ $ * * $ * * $ $ * $ * * * * * * * * * * * * * * * $ * $ $ * $ $ * * * * * * * * * * * * * * $ $ $ $ * $ $ $ $ $ * * * * * * * * * * * * * * * $ * * * * * * * * * * * * $ $ $ $ $ $ $ $ $ $ $ $ $ * * * $ * * * * * * * * * * * * * * * * * * * * * * * * $ $ $ $ $ * $ $ $ $ $ $ $ $ $ $ $ $ $ G * * * $ $ $ $ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * =end
