Another version:

use strict;
use warnings;
my $grid = join('', <DATA>);
$grid =~ s/\n//g;
my $n = sqrt(length $grid);
my @sqs;
while( $grid =~ /(.*?)[.x]/ ) {
  my $sq = ('A'..'Z')[scalar(@sqs)%26];
  my $pos = length $1;
  substr( $grid, $pos, 1 ) = '.';
  my $i = 1;
  my $x = $pos%$n;
  my $y = int $pos/$n;
  $i++ while $x+$i < $n and $y+$i < $n and join( '', map { substr($gri
+d,$_*$n+$x,$i+1) } $y..$y+$i ) eq '.' x (($i+1)*($i+1));
  substr($grid,$_*$n+$x,$i) = $sq x $i for $y..$y+$i-1;
  push @sqs, [ $x+1, $y+1, $i, $sq ];
  $sq++;
}
print substr($grid,$n*$_,$n)."\n" for 0..$n-1;
print "@$_\n" for @sqs;
__DATA__
............
.........x..
......x.....
..x.........
x...........
....x.......
.......xx...
..x.........
..x.....x...
..x.........
.x.....x....
............
[download]