#!/bin/perl

use strict;
use warnings;
use Data::Dumper;

my $grid = [[0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
            [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
            [1,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0],
            [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],
            [0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,0],
            [0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
           ];


sub get_area {
   my $sel_area = 0;
   my ($grid, $x1, $y1, $x2, $y2) = @_;
   for my $x ($x1..$x2) {
      for my $y ($y1..$y2) {
         $sel_area++ if $grid->[$x][$y] eq "1";
     }
   }
   return $sel_area;
}

sub sel_area {
   my $sel_area = 0;
   my ($grid, $label,$x1, $y1, $x2, $y2) = @_;
   die unless defined $x1 and defined $y1 and defined $x2 and defined $y2;
   for my $x ($x1..$x2) {
      for my $y ($y1..$y2) {
         $grid->[$x][$y] = $label;
     }
   }
   return $sel_area;
}



my ($min_x , $min_y,$max_x, $max_y) = (0,0,15,15);

my $area = get_area($grid, $min_x, $min_y,$max_x, $max_y);
my $sel_area = 0;

sub print_grid {
   my $grid = shift;
   for my $row (@$grid) {
      for my $item (@$row) {
         print( $item eq '0' ? '.' : $item );
      }
      print "\n";
   }
}

print "Selected area: $area\n";
print_grid($grid);
print "\n", "X" x 16, "\n\n";

my ($s_x, $s_y) = ($min_x, $min_y);
my $boxes;
my $l = 'a';
while ($sel_area < $area) {
   if ($grid->[$s_x][$s_y] eq "1") {
      my ($t_x,$t_y) = ($s_x, $s_y);
      while (1) {
         last if ($grid->[$t_x+1][$s_y] ne '1');
         $t_x++;
      }
      while (1) {
         $t_y++; 
         my ($trial_area, $real_area) = (
            get_area($grid, $s_x, $s_y, $t_x, $t_y),
            ( ($t_x - $s_x + 1) * ($t_y - $s_y + 1) )   
            );
         if ($trial_area < $real_area) {
            $t_y--;
            last;
         };
      }
      $sel_area += get_area($grid, $s_x, $s_y, $t_x, $t_y);
      sel_area($grid, $l, $s_x, $s_y, $t_x, $t_y);
      push @$boxes, [ $s_x, $s_y, $t_x, $t_y ];
      $l ++;
   }
   last if $sel_area == $area;
   $s_x++;
   if ($s_x > $max_x) {
      $s_x = $min_x;
      $s_y++;
      if ($s_y > $max_y) {
         die "Failed"
      }
   }
}


print_grid($grid);
print "\n";
print Dumper($boxes);

##</code><code>##

Selected area: 38
.111............
1111............
1111........1...
1111............
................
................
................
.........1111...
...........11...
...........11...
............111.
..1111......111.
..1111..........
................
................
................

XXXXXXXXXXXXXXXX

.bbb............
aaaa............
aaaa........f...
aaaa............
................
................
................
.........dddd...
...........ee...
...........ee...
............ggg.
..cccc......ggg.
..cccc..........
................
................
................

$VAR1 = [
          [ 1, 0, 3, 3 ],
          [ 0, 1, 0, 3 ],
          [11, 2,12, 5 ],
          [ 7, 9, 7,12 ],
          [ 8,11, 9,12 ],
          [ 2,12, 2,12 ],
          [10,12,11,14 ]
        ];