class Maze
  
  
  
  def solve

    
    reset_visiting_state

    
    @queue = []
    enqueue_cell([], @start_x, @start_y)

    
    
    path = nil
    until path || @queue.empty?
      path = solve_visit_cell
    end

    if path
      
      for x, y in path
        @path[x][y] = true
      end
    else
      puts 
    end
  end

  private

  
  def solve_visit_cell
    
    path = @queue.shift
    
    x, y = path.last

    
    return path  if x == @end_x && y == @end_y

    
    @visited[x][y] = true

    for dx, dy in DIRECTIONS
      if dx.nonzero?
        
        new_x = x + dx
        if move_valid?(new_x, y) &&!@vertical_walls[ [x, new_x].min ][y]
          enqueue_cell(path, new_x, y)
        end
      else
        
        new_y = y + dy
        if move_valid?(x, new_y) &&!@horizontal_walls[x][ [y, new_y].min ]
          enqueue_cell(path, x, new_y)
        end
      end
    end

    nil         
  end

  
  def enqueue_cell(path, x, y)
    
    @queue << path + [[x, y]]
  end
end


maze = Maze.new 20, 10
maze.solve
maze.print