迷路の最短経路

ここにある迷路の最短経路を調べる問題をやってみた。これはまた要するに動的計画法でいいんでしょ、とハンマーの使い方を覚えたもんだからすべてが釘に見える感じで、同じ方法論でやってみようとしてみたり。ダイクストラ法がうんたらという話も聞こえてきたけど、ちょっと大げさっぽい。

で、ともかく書いてみて1時間ほど試行錯誤したのち、うまく行かずに放置していたのだけど、スタートとゴールは実は対象なのだよ、どっちからはじめても同じだよ、という神の声が聞こえて、別の方針でやってみることにした。

スタートから隣接するセルを1つずつ辿っていき、適当に埋めていく。すでに誰かがそのセルに来たことがあれば、その経路は調べる必要がない。

この方針自体は上手くいきそうだとすぐにわかったけど、実際に動くコードに落とし込むのにえらい時間がかかってしまった。いろいろ思うところはあるけど、動いて良かった。

=begin
example maze:
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

output(shortest path):
**************************
*S* *####                *
*#* *# *# *************  *
*#*###* #  ************  *
*### *  #######          *
**************#***********
* #############          *
**#***********************
* ###  *##############G  *
*  *##### *********** *  *
*    *        ******* *  *
*       *                *
**************************
=end

Point = Struct.new(:y, :x)

def read_maze
  maze = []
  while line = gets
    line.chomp!
    maze << line.split(//)
  end
  maze
end

def find_postion(maze, c)
  line = maze.find {|l| l.index(c)}
  y = maze.index(line)
  x = line.index(c)
  return Point.new(y, x)
end

def next_cell(paths, maze, table)
  new_paths = []
  paths.each do |path|
    [[-1, 0], [1, 0], [0, -1], [0, 1]].each do |move|
      p = path.last
      y2 = p.y + move[0]
      x2 = p.x + move[1]
      if (table[y2][x2] == nil &&
          (maze[y2][x2]  == " " || maze[y2][x2] == "G")) then
        table[y2][x2] = table[p.y][p.x] + 1
        new_path = Marshal.load(Marshal.dump(path))
        new_path << Point.new(y2, x2)
        new_path << "goal" if maze[y2][x2] == "G"
        new_paths << new_path
      end
    end
  end
  new_paths
end

# initialize

maze = read_maze
# maze = [["*", "*", "*", "*", "*"], ["*", "S", " ", " ", "*"], ["*", " ", " ", "G", "*"], ["*", "*", "*", "*", "*"]]

table = Array.new(maze.size) do Array.new(maze[0].size, nil) end
# table = [[nil, nil, nil, nil, nil], [nil, nil, nil, nil, nil], [nil, nil, nil, nil, nil], [nil, nil, nil, nil, nil]]

start = find_postion(maze, "S")
table[start.y][start.x] = 0
paths = [[start]]   # [[start,p1],[start,p2]] -> [[start,p1,p3],[start,p2,p4]]

# search cell by cell

while true do
  paths = next_cell(paths, maze, table)

  # if some path hits the goal then.
  paths.each do |path|
    if path.last == "goal" then
      path.pop             # need to delete the "goal"
      path.pop; path.shift # just to output S and G
      path.each do |p|
        maze[p.y][p.x] = "#"
      end
      maze.each do |line|
        print line.join,"\n"
      end
      exit
    end
  end
end