// Recursive Backtracking Maze Generator
// Based on DWScript unit test implementation
SetRandSeed(42);

procedure MakeMaze(size : Integer);
require
   size >= 1;
begin
   var cells : array of Boolean;
   type TMovement = record
      Start : Integer;
      Direction : Integer;
   end;
   var stack : array of TMovement;
   var m : TMovement;

   var n := 2*size + 1;
   cells.SetLength(Sqr(2*size + 1));
   var toVisit := size*size;

   var x := RandomInt(size);
   var y := RandomInt(size);
   var p := (1 + 2*x) + (1 + 2*y) * n;

   while True do begin
      x := (p mod n) div 2;
      y := (p div n) div 2;
      cells[p] := True;
      toVisit -= 1;
      if toVisit = 0 then break;

      var directions : array of Integer = [];
      if (x > 0) and not cells[p-2] then
         directions.Add(-2);
      if (y > 0) and not cells[p-2*n] then
         directions.Add(-2*n);
      if (x < size-1) and not cells[p+2] then
         directions.Add(2);
      if (y < size-1) and not cells[p+2*n] then
         directions.Add(2*n);
      
      // Shuffle directions
      for var i := directions.High downto 1 do
         directions.Swap(i, RandomInt(i+1));
         
      for var dir in directions do begin
         m.Start := p;
         m.Direction := dir;
         stack.Add(m); // Use Add instead of Push for standard dynamic array
      end;

      var found := False;
      while stack.Length > 0 do begin
         m := stack[stack.High]; // Peek
         stack.SetLength(stack.Length - 1); // Pop
         p := m.Start;
         if not cells[p + m.Direction] then begin
            cells[p + m.Direction div 2] := True;
            p += m.Direction;
            found := True;
            break;
         end;
      end;
      if not found then break;
   end;

   PrintLn('Maze ' + IntToStr(size) + 'x' + IntToStr(size) + ':');
   for var i := 0 to cells.High step n do begin
      for var j := 0 to n-1 do
         if cells[i+j] then
            Print('  ')
         else Print('##');
      PrintLn('');
   end;
end;

MakeMaze(10);