Задача з мікропроцесором

Відома компанія-виробник мікропроцесорів звернулася до вас із проханням розмістити деякі змінні компоненти (віджети) на своїх комп'ютерних чіпах. Кожен чіп має вигляд квадрату N \times N слотів. В один слот може бути вставлений лише один компонент, і вам потрібно розмістити якомога більше віджетів.

Звичайно, сучасні процесорні схеми складні. На жаль, існує кілька обмежень:

• Деякі слоти вимкнені.

• Деякі слоти вже зайняті іншими компонентами й не можуть використовуватись для віджетів.

• До горизонтальних і вертикальних країв чіпа підключені паралельні шини пам'яті, навантаження яких має бути збалансованим. Тобто, у першому рядку має бути стільки ж компонентів, скільки і в першому стовпці; у другому рядку — стільки ж, як і в другому стовпці і так далі. Кількість компонентів включає як уже розміщені на чіпі, так і нові віджети.

• Також джерела живлення підключені до кінців кожного рядка і стовпця. Щоб уникнути перегріву, в будь-якому рядку або стовпці має бути не більше, ніж $A/B$ від загальної кількості компонентів на чіпі.

Опис чіпа складається з $N$ рядків по $N$ символів, де '.' позначає вільний слот, '/' — вимкнений слот, а 'C' — слот, зайнятий компонентом. Наприклад:

CC/.. ./.// ..C.C /.C.. /./C/

Якщо в будь-якому рядку або стовпці не може бути більш ніж $3/10$ компонентів, то максимальна кількість віджетів, які можна додати до цього 5 \times 5 чіпа, дорівнює $7$. Один з можливих варіантів розміщення показано нижче, де 'W' — віджет, доданий у порожній слот.

CC/W. W/W// W.C.C /.CWW /W/C/