【Ruby】【アルゴリズム】ダイクストラ法。迷路をとく。

　
この記事に迷路の問題が載っていたよ

問題

壁とスペースで構成された迷路が与えられたとき、
スタート地点からゴール地点に至る最短経路を求めよ

　
データ構造をどう作ればいいかな。

ちなみに。。

ぶっちゃけ、３時間かけてこれ（回答不達）ということはコードを書く能力は０でしょ？

やばい。
　
たぶん同期のうち95％くらいは解けないと思うけど。。。

知らないと解けないよ。

ポイント

全迷路情報をただの文字列として@data_stringに、
空白箇所の情報をグラフ構造として@nodesに表現。

"***************************S* *         *       ･･･
[#<Node:0x2efd850 @id=27, @ch="S", @edges=[53], @cost=nil, @done=false, @from=nil>, #<Node:0x2efd718 @id=29, @ch=" ", @edges=[55], @cost=nil, @done=false, @from=nil>,･･･

　
最終的に@nodesの情報を@data_stringに統合する

(HEIGHT*SIDE).times do |i|
  node = @nodes.find{|node|node.id == i }
  @data_string[i] = node.ch if node
end

　
ダイクストラ法で最適解を求めています。

loop do
  next_node = nil
  @nodes.each do |node|
    next if node.done || node.cost.nil?
    next_node = node if next_node.nil? || node.cost < next_node.cost
  end
  break if next_node.nil?
･･･

コード全量

data= DATA.readlines.map{ |line| line.chomp }
SIDE = data[0].length
HEIGHT = data.length
class Node
  def initialize(id, ch, edges, cost=nil, done=false, from=nil)
    @id, @ch, @edges, @cost, @done, @from  = id, ch, edges, cost, done, from
  end
  attr_accessor :id, :ch, :edges, :cost, :done, :from
end
class Maze
  def initialize(data)
    @nodes = []
    @data_string = data.join("")
    @data_string.split("").each_with_index do |ch, i|
      if ch != "*"
        edges = []
        edges << i-1  if @data_string[i-1]!="*"
        edges << i-SIDE if i-SIDE >=0 && @data_string[i-SIDE]!="*"
        edges << i+1  if @data_string[i+1]!="*"
        edges << i+SIDE if i+SIDE <=(SIDE*HEIGHT) && @data_string[i+SIDE]!="*"
        @nodes << Node.new(i, ch, edges)
      end
    end
    p @data_string
    p @nodes
  end
  def solve(start)
    @nodes.each do |node|
      node.cost = node.ch==start ? 0 : nil
      node.done, node.from = false, nil
    end
    loop do
      next_node = nil
      @nodes.each do |node|
        next if node.done || node.cost.nil?
        next_node = node if next_node.nil? || node.cost < next_node.cost
      end
      break if next_node.nil?
      #@nodesを更新
      next_node.done = true
      next_node.edges.each do |edge_id|
        reachble_node = @nodes.find { |node| node.id == edge_id }
        reachble_cost = next_node.cost + 1
        if reachble_node.cost.nil? || reachble_cost < reachble_node.cost
          reachble_node.cost = reachble_cost
          reachble_node.from = next_node.id
        end
      end
    end
  end
  def show(goal)
    passage = @nodes.find{|node|node.ch == goal }
    while passage = @nodes.find{|node|node.id == passage.from }
      passage.ch = "$" if passage.ch != "S"
    end
#@node の情報を @data_string に統合
(HEIGHT*SIDE).times do |i|
  node = @nodes.find{|node|node.id == i }
  @data_string[i] = node.ch if node
end
    HEIGHT.times do |i|
      puts @data_string[i*SIDE, SIDE]
    end
  end
end
maze = Maze.new(data)
maze.solve("S")
maze.show("G")

__END__
**************************
*S* *         *          *
* * *  *  ***** *** **   *
* *   *    **** *** ***  *
*    *            *      *
***** * ************* ****
****     *** ****     ****
***** * ************* ****
****     *** ****     ****
***** * ************* ****
****     *** ****     ****
** ********* **** *** ****
*      *             *G  *
*  **     *********** *  *
*    *  ***** *******    *
****                   * *
**************************

　
■実行結果

**************************
*S* *$$$$$    *$$$$$     *
*$* *$ * $*****$***$**   *
*$*$$$*  $$****$***$***  *
*$$$ *    $$$$$$  *$$$   *
***** * *************$****
****     *** ****    $****
***** * *************$****
****     *** ****    $****
***** * *************$****
****     *** ****$$$$$****
** ********* ****$*** ****
*      *$$$$$$$$$$   *G$ *
*  **  $$ *********** *$ *
*    * $***** *******$$$ *
****   $$$$$$$$$$$$$$$ * *
**************************