gistfile1.rb

#http://www.logos.t.u-tokyo.ac.jp/www/home/chik/algorithm-design/08%20Graph%20Algorithms.pdfの38枚目を参考に
class OKAJIMA
  def initialize(file_path)
    @maze = Array.new()
    open(file_path).each do |l|
      @maze.push l.chomp.split(//)
    end

    @cost = Hash.new(1/0.0)
    @det = Hash.new()
    @from = Hash.new{}
    @route = []
    @start = []
    @goal = []
    
    @maze.each_index do |i|
      @maze[i].each_index do |j|
        @det[[i, j]] = false
        if @maze[i][j] == "*"
          @cost[[i, j]] = false
          @det[[i, j]] = true
        elsif @maze[i][j] == "S"
          @start = [i, j]
          @cost[@start] = 0
          @det[@start] = true
        elsif @maze[i][j] == "G"
          @goal =  [i, j]
        end
      end
    end
  end

  def find_4(i, j)
    ret = []
    [-1,1].each do |x|
      ret.push [i+x, j] if @maze[i+x][j] && !@det[[i+x, j]]
    end
    
    [-1,1].each do |y|
      ret.push [i, j+y] if @maze[i][j+y] && !@det[[i, j+y]]
    end
    return ret
  end

  def search
    while @det.values.include?(false)
      tmp_list = []
      @det.select{|k, v| v && @cost[k]}.each do |hoge|
        i, j = hoge[0]
        edges = find_4(i, j)
        
        edges.each do |v|
          if @cost[v]  > @cost[[i, j]] + 1
            @cost[v] = @cost[[i, j]] + 1
            @from[v] = [i, j]
          end
          tmp_list.push [v, @cost[v]]
        end
      end
      @det[tmp_list.sort{|a,b|a[1] <=> b[1]}[0][0]] = true
    end
    
    @route.push @from[@goal]
    g_x, g_y = @route[-1]
    @maze[g_x][g_y] = "$"
    loop do
      back = @route[-1]
      break if @from[back] == @start
      @route.push @from[back]
      @maze[@route[-1][0]][@route[-1][1]] = "$"
    end
  end

  def show_maze
    @maze.each_index do |i|
      puts @maze[i].inject(""){|s,c|s+=c}
    end
  end
  
end

m = OKAJIMA.new("./map.txt")
m.search
m.show_maze