DouKaku?

class Maze
  WALL, VAC = '#', ' '
  DIRS = [[+1, 0], [-1, 0], [0, +1], [0, -1]]
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) { WALL*(2*@cols+1) }
  end

  def gen
    conn = Array.new(@rows) { Array.new(@cols, false) }
    cand = [[rand(@rows), rand(@cols), 0, 0]] # (0,0) is dummy
    until cand.empty?
      y, x, dy, dx = cand.slice!(rand(cand.size))
      next if conn[y][x]
      conn[y][x] = true
      @field[2*y+1-dy][2*x+1-dx] = VAC
      @field[2*y+1][2*x+1] = VAC
      DIRS.each do |mv|
        y_, x_ = y+mv[0], x+mv[1]
        if (0...@rows) === y_ &&
           (0...@cols) === x_ &&
           !conn[y_][x_]
          cand << [y_, x_, mv[0], mv[1]]
        end
      end
    end
    self
  end

  def p
    puts @field
  end
end

M, N = 10, 10
maze = Maze.new(M, N)
maze.gen.p