迷路を解くスクリプト - どっかのブログの問題

maze.rb

#!/usr/bin/ruby
class Pos
  include Enumerable
  attr_reader :x, :y, :route

  def initialize (x, y)
    @x, @y, @route = x, y, []
  end

  def each (&block)
    [[0, 1], [0, -1], [1, 0], [-1, 0]].each {|dx, dy| block.call(Pos.new(x + dx, y + dy)) }
  end
end

class Maze
  attr_reader :start

  def initialize
    @maze = []
  end

  def inspect
    @maze.map(&:join).join("\n")
  end

  def dup
    self.clone.tap{|it| it.instance_variable_set(:@maze, @maze.map(&:dup)) }
  end

  def read (guard = false)
    ml, y = 0, 1
    while line = ARGF.gets
      line.chomp!
      if guard
        line = "*#{line}*"
        ml = line.size if ml < line.size
      end
      sp = line =~ /S/
      @start = Pos.new(sp, y) if sp
      @maze << line.split(//)
      y += 1
    end
    if guard
      @maze.unshift(['*'] * ml)
      @maze.push(['*'] * ml)
    end
  end

  def at (pt)
    @maze[pt.y][pt.x]
  end

  def set (pt, v)
    @maze[pt.y][pt.x] = v
  end

  def draw_route (route)
    r = dup
    route[1..-1].each do
      |pt|
      r.set(pt, '$')
    end
    r
  end
end

class Head < Pos
  attr_reader :parent

  def initialize (pt, parent = nil)
    super(pt.x, pt.y)
    @parent = parent
  end

  def route
    r = []
    n = self
    while n
      r << n
      n = n.parent
    end
    r
  end
end

class Solver
  attr_reader :maze

  def initialize (maze)
    @maze = maze.dup
    @heads = [Head.new(maze.start)]
  end

  def step
    nexts = []
    @heads.each do
      |head|
      head.each {|pt| return Head.new(pt, head) if maze.at(pt) == 'G' }
      head.find_all {|pt| maze.at(pt) == ' ' } .each do
        |pt|
        maze.set(pt, '-')
        nexts << Head.new(pt, head)
      end
    end
    @heads = nexts
    return
  end

  def inspect
    maze.inspect
  end
end

maze = Maze.new
maze.read
solver = Solver.new(maze)
p solver until answer = solver.step
p maze.draw_route(answer.route)