http://okajima.air-nifty.com/b/2010/01/post-abc6.html の解答

maze.rb

# -*- coding: utf-8 -*-
require 'forwardable'

Address = Struct.new :x, :y do
  def self.[] x,y # Address[x,y]
    Address.new x,y
  end

  def adjoinings # 隣接アドレス
    x,y = self.x, self.y
    [[x,y-1],[x,y+1],[x-1,y],[x+1,y]].map{ |adr| Address.new *adr }
  end
end

Attribute = Struct.new :object, :distance, :agent_status do
  def space?
    object == ' '
  end

  def movable?
    object != '*'
  end

  def goal?
    object == 'G'
  end

  def measured?
    distance != nil
  end

  def lived?
    agent_status == 'L'
  end
end

class Map
  extend Forwardable
  def_delegators(:@nodes, :[], :[]=)
  def_delegators(:@strategy, :inspect)

  def initialize str=STR
    @nodes = {}
    class << @nodes
      def [] *keys # @nodes[x,y] OR @nodes[Address[x,y]]
        if keys.size == 1 # 引数が Address[x,y] の場合
          super(keys.first)
        else
          super(Address[*keys])
        end
      end

      def []= *keys,atr # @nodes[x,y] = OR @nodes[Address[x,y]] =
        if keys.size == 1 # 引数が Address[x,y] の場合
          super(keys.first, atr)
        else
          super(Address[*keys], atr)
        end
      end
    end

    parse str
  end

  def step
    case
    when @strategy.nil?
      @strategy = Measure.new self
    when @strategy.finish? && @strategy.class == Measure
      @strategy = Agent.new self
    when @strategy.finish? && @strategy.class == Agent
      @finish = true
      return print result
    else
      @strategy.step
    end
  end

  def finish?
    @finish == true
  end

  def max coordinate # max :x OR max :y
    @nodes.keys.map(&coordinate).max
  end

  def to_a
    (0..max(:y)).map do |row_num|
      (0..max(:x)).map do |col_num|
        @nodes[col_num, row_num]
      end
    end
  end

  def search obj, attribute=:object
    @nodes.select{|k,v| v.send(attribute) == obj}
  end

  def start_node
    select_node 'S'
  end

  def goal_node
    select_node 'G'
  end

  def result
    manipulate = lambda{ |e|
      if e.space? && e.agent_status == 'L'
        '$'
      else
        e.object
      end
    }
    "\n" << to_a.map{|line| "#{line.map(&manipulate).join}\n"}.join
  end

  private
  def select_node target, return_value=:attribute
    base = search(target)
    case return_value
    when :address
      base.keys.first
    when :attribute
      base.values.first
    end
  end

  def parse str
    base_ary = str.split("\n").map{|line| line.split(//)}
    base_ary.each_with_index do |row,row_num|
      row.each_with_index do |col,col_num|
        @nodes[col_num, row_num] = Attribute.new col
      end
    end
  end
end

class Measure
  def initialize map
    @distance = 0
    @map = map
    @map.start_node.distance = 0
  end

  def step
    return self if finish?

    base_address = @map.search(@distance, :distance).keys
    adjoining_address = base_address.map(&:adjoinings).flatten.uniq

    adjoining_address.each do |address|
      needs_measure = @map[address].movable? && !@map[address].measured?
      record(address, @distance + 1) if needs_measure
    end

    @distance += 1
    self
  end

  def inspect
    manipulate = lambda{ |e|
      "%2s" % (e.space?? e.distance||' ' : e.object)
    }
    "#{self.class}\n" << @map.to_a.map{ |line| "#{line.map(&manipulate).join}\n" }.join \
    << "@distance=#{@distance}" \
    << "\nfinish?=#{finish?}"
  end

  def finish?
    @map.search(@distance, :distance).values.any?(&:goal?)
  end

  private
  def record address, distance
    @map[address].distance = distance
  end
end

class Agent
  def initialize map
    @map = map
    @map.goal_node.agent_status = 'L'
    @target = @map.goal_node.distance
  end

  def step
    return self if finish?

    base_address = @map.search('L', :agent_status).keys
    adjoining_address = base_address.map(&:adjoinings).flatten.uniq.reject{ |adr| @map[adr].distance.nil? }

    adjoining_address.each do |address|
      next if @map[address].lived?
      if @map[address].distance < @target
        record(address, 'L')
        break # 有効な道は一つだけ用意する
      else
        record(address, 'D')
      end
    end

    @target -= 1
    self
  end

  def inspect
    manipulate = lambda{ |e|
      "%2s" % (e.space?? e.agent_status||e.distance : e.object)
    }
    "#{self.class}\n" << @map.to_a.map{ |line| "#{line.map(&manipulate).join}\n" }.join \
    << "@target=#{@target}" \
    << "\nfinish?=#{finish?}"
  end

  def finish?
    @target == 0
  end

  private
  def record address, status
    @map[address].agent_status = status
  end
end

STR = <<__EOS__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
__EOS__

if $0 == __FILE__
  m = Map.new
  m.step until m.finish?
end