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

@author Brent Newey
@created 2010.07.06 11:00:21
@modified 2010.07.06 15:02:36

<description>
"""
import copy
import sys
from math import pow, sqrt
from numpy import array

BERRY_VAL = 1
EMPTY_VAL = 0
EDGE_VAL = 0
HOUSE_VAL = 0
ME_MULT = 5
NEW_COST = 5
BERRY_GAIN_VAL = 30
DENSITY_VAL = 10

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

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

class StrawberryField():

    def __init__(self, size, field, perp_val=1, expansion_val=1, new_val=1, cluster_val=1, greenhouse_limit=None):
        self.size = size
        self.count = 0
        self.housechar = 'A'
        self.field = field
        self.perp_val = perp_val
        self.expansion_val = expansion_val
        self.cluster_val = cluster_val
        self.new_val = new_val
        if greenhouse_limit:
            self.size = min(self.size, greenhouse_limit)
        self.max_x = len(self.field[...]) - 1
        self.max_y = len(self.field[0]) - 1
        self.max_d = distance(0, 0, self.max_x, self.max_y)

    # def score_square(self, x, y, berry_val=BERRY_VAL, empty_val=EMPTY_VAL, edge_val=EDGE_VAL, house_val=HOUSE_VAL):
    #     if 0 <= x <= self.max_x and 0 <= y <= self.max_y:
    #         if self.field[x, y] == '@':
    #             return berry_val
    #         elif self.field[x, y] in 'ABCDEFGHIJ':
    #             return house_val
    #         else:
    #             return empty_val
    #     else:
    #         return edge_val

    def score_square(self, x, y, density_val=DENSITY_VAL):
        if self.field[x, y] in 'ABCDEFGHIJ':
            return None
        score = 0.0
        max_score = 0.0
        for x2 in range(self.max_x + 1):
            for y2 in range(self.max_y + 1):
                if self.field[x2, y2] == '@':
                    dist = distance(x, y, x2, y2)
                    if dist == 0:
                        score += 3
                    else:
                        addscore = 1 / (dist * self.cluster_val)
                        if x == x2 or y == y2:
                            addscore *= self.perp_val
                        score += addscore
        return score

    def score_new_house(self, x, y):
        if self.count == self.size:
            return None

        score = self.score_square(x, y)
        if score:
            return score * self.new_val# * ME_MULT, house_val=None)
        # if me is None:
        #     return None

        # left = self.score_square(x, y - 1)
        # right = self.score_square(x, y + 1)
        # up = self.score_square(x - 1, y)
        # down = self.score_square(x + 1, y)

        # return float(me + left + right + up + down - NEW_COST)

    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
                        if self.field[exp_x, exp_y] == '@':
                            berries += 1
                        territory += 1
                    else:
                        return None
#        print housechar, dir_x, dir_y, berries, territory
        return (float(berries) / float(territory)) * (BERRY_GAIN_VAL / ((territory - berries) + 1)) * self.expansion_val
                        
    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

    def new_house_moves(self):
        moves = []
        for x in range(self.max_x + 1):
            for y in range(self.max_y + 1):
                score = self.score_new_house(x, y)
                if score is not None:
                    moves.append((score, ('new', x, y)))
        return moves

    def expand_house_moves(self):
        moves = []
        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 = self.score_expand_house(hc, e[0], e[1])
                if score is not None:
                    moves.append((score, ('expand', hc, e[0], e[1])))
        return moves

    def moves(self):
        possible = self.new_house_moves() + self.expand_house_moves()
        return sorted(possible, key=lambda p: p[0], reverse=True)

    def run(self):
        moves = self.moves()
        while moves and moves[0]:
            if not self.count_berries():
                break
            print moves[0]
            if moves[0][1][0] == 'new':
                print moves
            self.execute_move(moves[0][1])
            self.print_field()
#            raw_input()
            moves = self.moves()

    def execute_move(self, move):
        if move[0] == 'new':
            self.field[move[1], move[2]] = self.housechar
            self.housechar = chr(ord(self.housechar) + 1)
            self.count += 1
        else:
            expansions = []
            for x in range(self.max_x + 1):
                for y in range(self.max_y + 1):
                    if move[1] == self.field[x, y]:
                        expansions.append((x + move[2], y + move[3]))
            for e in expansions:
                self.field[e[0], e[1]] = move[1]

    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 add_run(runs, run):
    run.run()
    run.calculate_cost()
    runs.append(run)

if __name__ == "__main__":
    jumpto = 3
    with open('rectangles.txt', 'r') as fp:
        while 1:
            read = readfp(fp)
            if not read:
                exit()
            else:
                size, field = read
            if jumpto:
                jumpto -= 1
                continue
            runs = []
#            add_run(runs, StrawberryField(size, copy.copy(field)))
            add_run(runs, StrawberryField(size, copy.copy(field), perp_val=5, expansion_val=5))
            # runs[0].run()
            # runs[0].calculate_cost()
            # runs.append(StrawberryField(size, copy.copy(field), perp_val=5))
            # runs[1].run()
            # runs[1].calculate_cost()
            for i in range(1, size + 1):
                print i
                add_run(runs, StrawberryField(size, copy.copy(field), greenhouse_limit=i, cluster_val=5, perp_val=5))
            # runs.append(
            # runs[len(runs) - 1].run()
            # runs[len(runs) - 1].calculate_cost()

            best = sorted(runs, key=lambda r: r.cost)[0]

            print best.cost
            best.print_field()
            raw_input()
            

#        self.readfile(fp)


    # for x in range(strawberries.max_x + 1):
    #     for y in range(strawberries.max_y + 1):
    #         print x, y, strawberries.score_new_house(x, y)