Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
絶対左折禁止の迷路を解く
class SolveMaze
open("maze_never_turn_left.txt") {|io| @@field = io.readlines}
@@field.map! {|f| " " + f.chomp + " "}
a = [" " * @@field[0].size]
@@field = a + @@field + a
class Position
def initialize(x, y, dir = nil, parent = nil)
@x, @y = x, y
@kind = get[y][x]
@dir = dir
@parent = parent
end
attr_reader :x, :y, :dir, :parent, :kind
def neighbor
result = []
[[0, -1], [1, 0], [0, 1], [-1, 0]].each_with_index do |step, i|
x = @x + step[0]
y = @y + step[1]
result << Position.new(x, y, i, self) if get[y][x] != " "
end
result
end
def get
SolveMaze.class_variable_get(:@@field)
end
def finish
result = [[@x, @y]]
a = parent
field = Marshal.load(Marshal.dump(get))
loop do
result << [a.x, a.y]
break if a.kind == "S"
field[a.y][a.x] = %w(↑ → ↓ ←)[a.dir]
a = a.parent
end
#puts result.reverse.flatten.join(",")
field.map {|x| x.gsub!("0", " ")}
field.each {|x| puts x}
#exit
end
def check
a = self
loop do
a = a.parent
return true if a.kind == "S"
return false if a.x == @x and a.y == @y and a.dir == @dir
end
end
end
def initialize
n = @@field.join.index("S")
l = @@field[0].length
@queue = Position.new(n % l, n / l).neighbor
end
def go
while (po = @queue.shift)
pos = po.neighbor.reject {|a| a.dir == (po.dir + 2) % 4} #あと戻り以外に行ける場所
pos.each do |nxt|
next if (po.dir - nxt.dir) % 4 == 1 #左折禁止
if nxt.kind == "G"
nxt.finish
elsif nxt.kind == "0" and (pos.size < 2 or nxt.check)
@queue << nxt
end
end
end
end
end
SolveMaze.new.go
0000000000000000 00000000000
0 0 0 0 0 0 0
00S 0000000000000000 0 0
0 0 0 0 000000
0 0 000000 0 0
0 0000 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0000 00000 0 0 0 0
0 0 0 00000000000 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0000000000 0 00000000000
0 0 0 0 0 0 0
000000 00000000 00000000000
0 0 0 0 0
0 0 0 0 0
0 000000000000000000 00000000
0 0 0 0 0 0 0 0 0
0 000000 0 000000000000 0
0 0 0 0 0 0
0 00000000000000000 G00
0 0 0 0 0 0
0 0 0 0 0 0
00000000 0000000000000000000
require 'cairo'
L = 20
Margin = 30
maze = open("maze_never_turn_left.txt") {|io| io.readlines}.map(&:chomp)
Width = (w = maze[0].length) * L + Margin * 2
Height = (h = maze.size) * L + Margin * 2
surface = Cairo::ImageSurface.new(Width, Height)
c = Cairo::Context.new(surface)
c.set_source_rgb(1, 1, 1)
c.rectangle(0, 0, Width, Height)
c.fill
h.times do |y|
w.times do |x|
if maze[y][x] == "0"
c.set_source_rgb(0, 0, 0)
elsif maze[y][x] != " "
c.set_source_rgb(1, 0, 0)
end
if maze[y][x] != " "
c.rectangle(Margin + x * L, Margin + y * L, L, L)
c.fill
end
end
end
c.target.write_to_png("./picture/route000.png")
data = File.read("maze_never_turn_left_result.txt").chomp.split(",").map(&:to_i).each_slice(2).to_a
co = 0
data.each_cons(2) do |p1, p2|
if p1[0] > p2[0] or p1[1] > p2[1]
c.set_source_rgb(1, 0, 1)
else
c.set_source_rgb(0, 1, 1)
end
if p1[0] == p2[0]
l = (p1[1] < p2[1]) ? p1[1] : p2[1]
x = Margin + L / 2 + (p1[0] - 1) * L - 1
y = Margin + L / 2 + (l - 1) * L
c.rectangle(x, y, 2, L)
else
l = (p1[0] < p2[0]) ? p1[0] : p2[0]
y = Margin + L / 2 + (p1[1] - 1) * L - 1
x = Margin + L / 2 + (l - 1) * L
c.rectangle(x, y, L, 2)
end
c.fill
c.target.write_to_png("./picture/route%03d.png" % (co += 1))
end
#カレントディレクトリに picture フォルダを作る
3,3,2,3,1,3,1,2,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10,1,11,1,12,1,13,1,13,2,13,3,13,4,13,5,13,6,13,7,13,8,13,9,13,10,13,11,13,12,12,12,11,12,10,12,9,12,9,11,9,10,9,9,9,8,9,7,9,6,9,5,9,4,9,3,10,3,11,3,12,3,13,3,14,3,15,3,16,3,17,3,18,3,19,3,20,3,20,4,20,5,20,6,20,7,20,8,20,9,19,9,18,9,17,9,16,9,15,9,14,9,13,9,13,8,13,7,13,6,13,5,14,5,15,5,16,5,16,6,16,7,16,8,16,9,16,10,16,11,16,12,16,13,16,14,15,14,14,14,13,14,12,14,11,14,10,14,9,14,9,13,9,12,10,12,11,12,12,12,12,13,12,14,12,15,12,16,12,17,12,18,12,19,12,20,12,21,11,21,10,21,9,21,8,21,7,21,6,21,5,21,4,21,4,20,4,19,5,19,6,19,7,19,8,19,8,20,8,21,8,22,8,23,8,24,7,24,6,24,5,24,4,24,3,24,2,24,1,24,1,23,1,22,1,21,1,20,1,19,1,18,1,17,1,16,1,15,1,14,2,14,3,14,4,14,5,14,6,14,6,15,6,16,6,17,6,18,6,19,5,19,4,19,3,19,3,18,3,17,4,17,5,17,6,17,7,17,8,17,9,17,10,17,11,17,12,17,13,17,14,17,15,17,16,17,17,17,18,17,19,17,20,17,20,18,20,19,19,19,18,19,17,19,16,19,16,18,16,17,16,16,16,15,16,14,16,13,16,12,16,11,16,10,16,9,17,9,18,9,19,9,20,9,21,9,22,9,23,9,23,10,23,11,23,12,22,12,21,12,20,12,20,11,20,10,20,9,20,8,20,7,20,6,20,5,20,4,20,3,20,2,20,1,21,1,22,1,23,1,24,1,25,1,26,1,27,1,28,1,29,1,30,1,30,2,30,3,30,4,30,5,30,6,30,7,30,8,30,9,30,10,30,11,30,12,30,13,30,14,29,14,28,14,27,14,26,14,25,14,24,14,23,14,22,14,21,14,20,14,20,13,20,12,21,12,22,12,23,12,24,12,25,12,26,12,27,12,27,13,27,14,27,15,27,16,27,17,27,18,27,19,26,19,25,19,24,19,23,19,23,18,23,17,24,17,25,17,26,17,27,17,28,17,29,17,30,17,30,18,30,19,30,20,30,21,29,21,28,21
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.