#!/usr/bin/env python2.6
""" strawberry.py

@author Brent Newey
@created 2010.07.06 11:00:21
@modified 2010.07.07 12:02:52

<description>
"""
import copy
# import sys
from math import pow, sqrt
from operator import itemgetter, attrgetter
from numpy import array

def distance(x1, y1, x2, y2):
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))

def readfp(fp):
    line = fp.readline()
    while line == '\n':
        line = fp.readline()
    try:
        size = int(line)
    except ValueError:
        return False
    rows = []
    line = fp.readline()
    readsomething = False
    while line:
        if line == '\n':
            if not readsomething:
                continue
            else:
                break
        rows.append(tuple(c for c in line if c != '\n'))
        line = fp.readline()
        readsomething = True
    if not rows:
        return False
    field = array(rows).T
    return size, field

class Rectangle():

    def __init__(self, x, y, w, h, area, density, squarity):
        self.x = x
        self.y = y
        self.w = w
        self.h = h
        self.area = area
        self.density = density
        self.squarity = squarity
        self.type = 'Rectangle'

class Expansion():

    def __init__(self, housechar, x, y):
        self.housechar = housechar
        self.x = x
        self.y = y
        self.squarity = 0
        self.type = 'Expansion'

class StrawberryField():

    def __init__(self, size, field):
        self.size = size
        self.count = 0
        self.housechar = 'A'
        self.field = field
        self.max_x = len(self.field[...]) - 1
        self.max_y = len(self.field[0]) - 1
        self.calculate_sbounds()

        self.house_rects = {}
#        self.max_d = distance(0, 0, self.max_x, self.max_y)

    def calculate_sbounds(self):
        self.min_sx = self.max_x
        self.max_sx = 0
        self.min_sy = self.max_y
        self.max_sy = 0
        for x in range(self.max_x + 1):
            for y in range(self.max_y + 1):
                if self.field[x, y] == '@':
                    self.min_sx = min(self.min_sx, x)
                    self.max_sx = max(self.max_sx, x)
                    self.min_sy = min(self.min_sy, y)
                    self.max_sy = max(self.max_sy, y)

    def print_field(self):
        for y in range(self.max_y + 1):
            linestr = ''
            for x in range(self.max_x + 1):
                linestr += self.field[x, y]
            print linestr

    def calculate_cost(self):
        self.cost = (ord(self.housechar) - ord('A')) * 10
        for x in range(self.max_x + 1):
            for y in range(self.max_y + 1):
                if self.field[x, y] in 'ABCDEFGHIJ':
                    self.cost += 1

    def calculate_house_rects(self):
        for i in range(ord(self.housechar) - ord('A')):
            self.house_rects[chr(i + ord('A'))] = self.get_house_rect(chr(i + ord('A')))

    def get_house_rect(self, housechar):
        xs, ys = [], []
        for x in range(self.max_x + 1):
            for y in range(self.max_y + 1):
                if self.field[x, y] == housechar:
                    xs.append(x)
                    ys.append(y)
        if not xs or not ys:
            return None
        x = min(xs)
        y = min(ys)
        w = max(xs) - x + 1
        h = max(ys) - y + 1
        return x, y, w, h

    def deconflict(self, housechar, rect):
        house_rect = self.house_rects[housechar]
        measure = False
        # if self.housechar == 'E' and housechar == 'C' and rect.x == 16 and rect.y == 5 and rect.w == 11 and rect.h == 2:
        #     print 'deconflicting'
        #     print housechar, house_rect
        #     print rect.x, rect.y, rect.w, rect.h
        #     measure = True
        if rect.x == house_rect[0] and rect.y == house_rect[1] and rect.x + rect.w == house_rect[0] + house_rect[2] and rect.y + rect.h == house_rect[1] + house_rect[3]:
            return False
        if rect.x > house_rect[0] and rect.x + rect.w < house_rect[0] + house_rect[2]:
            return False
        if rect.y > house_rect[1] and rect.y + rect.h < house_rect[1] + house_rect[3]:
            return False
        if rect.x < house_rect[0] and rect.x + rect.w < house_rect[0] + house_rect[2]:
            if rect.y < house_rect[1] and rect.y + rect.h < house_rect[1] + house_rect[3]:
                return False
            if rect.y > house_rect[1] and rect.y + rect.h > house_rect[1] + house_rect[3]:
                return False
        if rect.x > house_rect[0] and rect.x + rect.w > house_rect[0] + house_rect[2]:
            if rect.y > house_rect[1] and rect.y + rect.h > house_rect[1] + house_rect[3]:
                return False
            if rect.y < house_rect[1] and rect.y + rect.h < house_rect[1] + house_rect[3]:
                return False
        return True

    def rectangles(self, width, height):
        rects = []
        for x in range(self.max_sx + 2 - width):
            for y in range(self.max_sy + 2 - height):
                area = width * height
                squarity = abs(width - height)
                berries = 0
                total = 0
                territory = 0
                bummers = set()
                for x2 in range(width):
                    for y2 in range(height):
                        if self.field[x + x2, y + y2] in 'ABCDEFGHIJ':
                            bummers.add(self.field[x + x2, y + y2])
                        else:
                            territory += 1
                        if self.field[x + x2, y + y2] == '@':
                            berries += 1
                density = float(berries) / float(area)
                rect = Rectangle(x, y, width, height, area, density, squarity)
                failed = False
                if bummers:
                    for b in bummers:
                        success = self.deconflict(b, rect)
                        if not success:
                            failed = True
                if failed:
                    continue
                rect.cost = 10 + territory
                rect.value = berries
                rect.score = float(rect.value) / float(rect.cost)
                rects.append(rect)
        return rects, False

    def allrects(self):
        if self.count == self.size:
            return []
        rects = []
        for x in range(1, self.max_sx + 1):
            for y in range(1, self.max_sy + 1):
                r, stop = self.rectangles(x, y)
                rects += r
        return rects

    def score_expand_house(self, housechar, dir_x, dir_y):
        territory = 0
        berries = 0
        for x in range(self.max_x + 1):
            for y in range(self.max_y + 1):
                if self.field[x, y] == housechar:
                    exp_x = x + dir_x
                    exp_y = y + dir_y
                    if 0 <= exp_x <= self.max_x and 0 <= exp_y <= self.max_y:
                        if self.field[exp_x, exp_y] in 'ABCDEFGHIJ':
                            if self.field[exp_x, exp_y] == housechar:
                                continue
                            else:
                                return None, None
                        if self.field[exp_x, exp_y] == '@':
                            berries += 1
                        territory += 1
                    else:
                        return None, None
        if territory:
            return float(berries) / float(territory), territory
        else:
            return float(berries), territory

    def allexpansions(self):
        expansions = []
        for i in range(ord(self.housechar) - ord('A')):
            hc = chr(ord('A') + i)
            for e in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                score, territory = self.score_expand_house(hc, e[0], e[1])
                expansion = Expansion(hc, e[0], e[1])
                expansion.score = score
                expansion.territory = territory
                if score is not None:
                    expansions.append(expansion)
        return expansions

    def rescore_expansions(self, moves):
        berry_coords = []
        return_moves = []
        for x in range(self.min_sx, self.max_sx + 1):
            for y in range(self.min_sy, self.max_sy + 1):
                if self.field[x, y] == '@':
                    berry_coords.append([x, y])
        for move in moves:
            if isinstance(move, Rectangle):
                continue
            distances = []
            for x in range(self.max_x + 1):
                for y in range(self.max_y + 1):
                    if self.field[x, y] == move.housechar:
                        exp_x = x + move.x
                        exp_y = y + move.y
                        for coord in berry_coords:
                            distances.append(distance(exp_x, exp_y, coord[0], coord[1]))
            move.distance = min(distances)
#            print move.housechar, move.x, move.y, min(distances), move.territory, move.score
            return_moves.append(move)
        return return_moves

            

    def choose_move(self):
        moves = self.allrects() + self.allexpansions()
        moves.sort(key=attrgetter('score', 'squarity'), reverse=True)
        # if self.housechar == 'C':
        #     for m in moves[:10]:
        #         print 'moves', m.x, m.y, m.w, m.h, m.score, m.squarity

        move = moves[0]
        if move.score == 0.0:
            moves = self.rescore_expansions(moves)
            moves.sort(key=attrgetter('distance', 'territory'))

#            print moves[1].x, moves[1].y, moves[1].housechar, moves[1].score, moves[1].territory
            move = moves[0]
        return move

    def run(self):
        if not self.count_berries():
            return
        move = self.choose_move()
        while move:
            self.execute_move(move)
            self.calculate_house_rects()
            self.calculate_sbounds()
#            self.print_field()
#            raw_input()
            if not self.count_berries():
                break
            move = self.choose_move()
        
    def execute_move(self, move):
        if isinstance(move, Rectangle):
#            print 'Rectangle', move.x, move.y, move.w, move.h, move.score
            for x in range(move.x, move.x + move.w):
                for y in range(move.y, move.y + move.h):
                    self.field[x, y] = self.housechar
            self.housechar = chr(ord(self.housechar) + 1)
            self.count += 1
        else:
#            print 'Expansion', move.housechar, move.x, move.y, move.score, move.territory
            expansions = []
            for x in range(self.max_x + 1):
                for y in range(self.max_y + 1):
                    if move.housechar == self.field[x, y]:
                        expansions.append((x + move.x, y + move.y))
            for e in expansions:
                self.field[e[0], e[1]] = move.housechar

    def count_berries(self):
        berries = 0
        for x in range(self.max_x + 1):
            for y in range(self.max_y + 1):
                if self.field[x, y] == '@':
                    berries += 1
        return berries

if __name__ == "__main__":
    # jumpto = 5
    # doquit = True
    with open('rectangles2.txt', 'r') as fp:
        while 1:
            read = readfp(fp)
            if not read:
                exit()
            else:
                size, field = read
            # if jumpto:
            #     jumpto -= 1
            #     doquit = True
            #     continue
            field = StrawberryField(size, field)
            field.run()
            field.calculate_cost()
            print field.cost
            field.print_field()
            # if doquit:
            #     exit()