■「人材獲得作戦・４　試験問題ほか」を見てやってみた

この辺の迷路探索ができないソフト屋って何よ？話 -> http://app.cocolog-nifty.com/t/trackback/73665/47262245

実は最初深さ優先で作ってしまい、非最適な解き方で止まってしまっていた。

こういうのを30分切れないようでは駄目なんだろうな。

#!/usr/bin/ruby
move = [[-1,0],[1,0],[0,-1],[0,1]]
maze = $stdin.readlines.map{|s| s.chomp!}
maze.each_with_index do |row,i|
  if j = row.index("S"); S = [i,j]; end
  if j = row.index("G"); G = [i,j]; end
end

seen = {}
prev = {}
curr = [S]
until curr.include?(G)
  plan = []
  curr.each do |c|
    seen[c] = true
    move.map{|i,j| [c[0]+i, c[1]+j]}.each do |p|
      next if seen[p] || maze[p[0]][p[1]].chr == "*"
      prev[p] = c
      plan << p
    end
  end
  curr = plan
end

p = G
maze[p[0]][p[1]] = '#' while p = prev[p]
puts maze

Permalink | 記事への反応(1) | 02:07

ツイートシェア