絶対左折禁止の迷路を解く

maze_never_turn_left.rb

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

maze_never_turn_left.txt

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

maze_never_turn_left_make_result_png.rb

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 フォルダを作る

maze_never_turn_left_result.txt

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