jinzai.rb

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

ActiveRecord::Base.establish_connection(
  :adapter => 'sqlite3',
  :dbfile  => ':memory:'
)

class InitialSchema < ActiveRecord::Migration
  def self.up
    create_table :cells do |t|
      t.string :value
      t.integer :x
      t.integer :y
      t.integer :distance
    end

    add_index :cells, [:x, :y], :unique => true
  end

  def self.down
    drop_table :cells
  end
end

InitialSchema.migrate(:up)

class Cell < ActiveRecord::Base
  def self.parse_map(input)
    y = 0
    @map = {}
    input.chomp.split("\n").each{|line|
      x = 0
      line = line.chomp.split(//).each{|c|
        Cell.create(:value => c, :x => x, :y => y)
        x += 1
      }
      y += 1
      line
    }
  end

  def self.map
    y = 0
    result = []
    loop {
      cells = Cell.find(:all, :conditions => ['y = :y', {:y => y}], :order => 'x asc')
      return result if cells.empty?
      result << cells.map{|cell|
        cell.value
      }.join('')
      y += 1
    }
  end

  def around
    neighbor_diffs.map{|dx, dy|
      self.class.find_by_x_and_y(self.x + dx, self.y + dy)
    }.compact
  end

  def can_walk
    self.value == ' '
  end

  def is_start
    self.value == 'S'
  end

  def is_goal
    self.value == 'G'
  end

  def is_wall
    self.value == '*'
  end

  def neighbor_diffs
    [[-1, 0], [1, 0], [0,-1], [0,1]]
  end

  def prev
    neighbor_diffs.each{|dx, dy|
      cell = self.class.find_by_x_and_y_and_distance(self.x + dx, self.y + dy, self.distance-1)
      return cell if cell
    }
    nil
  end
end

Cell.parse_map(ARGF.read)

queue = []
start = Cell.find_by_value('S')
start.distance = 0
queue << start

while a = queue.pop
  a.around.each{|b|
    if (b.can_walk || b.is_goal) && (!b.distance || a.distance+1 < b.distance)
      b.distance = a.distance+1
      b.save
      queue.push(b)
     end
  }
end

goal = Cell.find_by_value('G')
raise 'no route to goal' unless goal.distance

route = goal
while route = route.prev
  break unless route.can_walk
  route.value = '$'
  route.save
end

puts Cell.map