迷路を解く

「人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。」で出題されている問題を解いてみた。

maze = []
dist = []
sx, sy, gx, gy = nil,nil,nil,nil
readlines.each_with_index do |l, y|
  next if l.chomp.empty?
  maze.push([])
  dist.push([])
  l.chomp.split(//).each_with_index do |c, x|
    maze.last.push(c)
    dist.last.push(-1)
    sx, sy = x, y if c == 'S'
    gx, gy = x, y if c == 'G'
  end
end

Direction = [[-1,0],[1,0],[0,-1],[0,1]]
que = []
que.push([0, sx, sy])
dist[sy][sx] = 0
until que.empty?
  d, x, y = *que.shift
  Direction.each do |dx, dy|
    tx, ty = x+dx, y+dy
    if maze[ty][tx] != '*' and dist[ty][tx] == -1
      que.push([d+1, tx, ty])
      dist[ty][tx] = d+1
    end
  end
end

x, y = gx, gy
until x == sx and y == sy
  maze[y][x] = '$' unless maze[y][x] == 'G'
  Direction.each do |dx, dy|
    tx, ty = x+dx, y+dy
    if dist[ty][tx] == dist[y][x] - 1
      x, y = tx, ty
      break
    end
  end
end

puts maze.inject(''){|r, l| r + l.join() + "\n"}

出力例

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

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

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

所要時間一時間ほど。
以前，この手の問題を解いたことがあるのに orz