Hack - 地下迷宮爆破ゲーム

タイトルは昔どこかで見かけた誤訳（explore を explode と空目したらしい）
各所で話題の 人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか をやってみた
id:SiroKuro:20100112:1263306170 あたりで指摘されてるように、塗り潰し法で

#!/usr/local/bin/ruby19
# coding:utf-8
# vi:set ts=3 sw=3:
# vim:set sts=0 noet:

require 'pp'

def read_maze filename
	lines = nil
	File.open filename do|file|
		lines = file.readlines
	end
	maze = []
	goal = nil
	y = 0
	lines.each do|line|
		line = line.chomp
		tmp = []
		x = 0
		line.each_char do|c|
			case c
			when '*'
				tmp << -1
			when ' '
				tmp << 0
			when 'S'
				tmp << 1
			when 'G'
				goal = [y, x]
				tmp << -2
			else
				raise "unknown char \"#{c}\""
			end
			x += 1
		end
		maze << tmp
		y += 1
	end
	[maze, goal]
end

def dump_maze maze
	maze.each do|line|
		line.each do|elem|
			case elem
			when -1
				print '*'
			when 0
				print ' '
			when 1
				print 'S'
			when -2
				print 'G'
			when -3
				print '$'
			else
				print (elem % 10).to_s
			end
		end
		print "\n"
	end
end

def next_maze maze, n
	newmaze = []
	y = 0
	maze.each do|line|
		tmp = []
		x = 0
		line.each do|elem|
			case elem
			when -1
				tmp << -1
			when 0
				if maze[y][x - 1] == n or maze[y][x + 1] == n or
					(maze[y - 1] and maze[y - 1][x]) == n or (maze[y + 1] and maze[y + 1][x]) == n then
					tmp << n + 1
				else
					tmp << 0
				end
			else
				tmp << elem
			end
			x += 1
		end
		newmaze << tmp
		y += 1
	end
	newmaze
end

def result_maze maze, goal
	maze = maze.dup
	pos = goal.dup
	n = maze[pos[0]][pos[1]]
	maze[pos[0]][pos[1]] = -2
	n -= 1
	while n > 1 do
		if maze[pos[0]][pos[1] - 1] == n then
			pos[1] -= 1
		elsif maze[pos[0]][pos[1] + 1] == n then
			pos[1] += 1
		elsif maze[pos[0] - 1] and maze[pos[0] - 1][pos[1]] == n then
			pos[0] -= 1
		elsif maze[pos[0] + 1] and maze[pos[0] + 1][pos[1]] == n then
			pos[0] += 1
		end
		maze[pos[0]][pos[1]] = -3
		n -= 1
	end
	maze.each_index do|y|
		maze[y].each_index do|x|
			if maze[y][x] > 1 then
				maze[y][x] = 0
			end
		end
	end
	dump_maze maze
end

maze, goal = read_maze 'input.txt'
#pp goal
#dump_maze maze
maze[goal[0]][goal[1]] = 0
#dump_maze maze
n = 1
maze_tmp = maze
while maze_tmp[goal[0]][goal[1]] == 0 do
	maze_tmp = next_maze maze_tmp, n
	#dump_maze maze_tmp
	n += 1
end
result_maze maze_tmp, goal

実行結果と所要時間

$ ./maze.rb
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************
$ ls -l
total 6
-rw-r--r--  1 ksmakoto  ksmakoto   351 Jan 17 10:37 input.txt
-rwxr-xr-x  1 ksmakoto  ksmakoto  2097 Jan 17 11:45 maze.rb

まぁこんなもんかな