Задача с микропроцессором
Известная компания по производству микропроцессоров попросила Вас разместить несколько взаимозаменяемых компонентов (виджетов) на компьютерных чипах. Каждый чип состоит из N×N квадратных слотов. Один слот может содержать только один компонент. Вам следует разместить на чипе как можно большее количество виджетов.
Конструкция современных процессоров довольно сложная. К несчастью, у Вас имеются следующие ограничения:
Некоторые слоты приведены в негодность и не работоспособны.
Некоторые слоты уже содержат другие компоненты и не могут использоваться для виджетов.
К вертикальным и горизонтальным концам чипа подсоединены шины памяти, поэтому должна быть учтена их пропускная способность. Поэтому в первой строке и в первом столбце должно находиться одинаковое количество компонентов, число компонент во второй строке и втором столбце также должно совпадать и так далее. При подсчете компонет следует учитывать как те, которые находились на чипе сначала, так и виджеты, которые были добавлены в пустые слоты.
К концам каждой строки и колонки чипа подключен источник питания. Для избежания перегрева каждая строка и колонка чипа должна содержать не более A/B компонент для заданных значений A и B.
Чип задается N строками по N символов каждая, где '.' указывает на пустой слот, '/' указывает на поврежденный слот, а 'C' указывает на то что слот уже занят компонентой. Например:
CC/.. ./.// ..C.C /.C.. /./C/
Если не более чем 3/10 компонент может находиться в каждой строке и каждом стобце, то наибольшее количество виджетов которое может быть добавлено к 5×5 чипу, равно 7. Возможное расположение представлено ниже, где через 'W' обозначается виджет, который добавлен в открытый слот.
CC/W. W/W// W.C.C /.CWW /W/C/
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается со строки, содержащей три целых числа: размер чипа N (1 ≤ N ≤ 10), и значения A и B (1 ≤ B ≤ 1000, 0 ≤ A ≤ B). Каждая из следующих N строк содержит N символов, описывающих слоты: '.', '/' или 'C'.
Последний тест завершается строкой, содержащей три ноля.
Выходные данные
Для каждого теста в отдельной строке вывести его номер. Если решение существует, то следует вывести максимальное количество виджетов, которое можно разместить на чипе. Вывести "impossible", если решения не существует.