11/04/2025 02:07:17

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2831. Сферы влияния

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Волшебная страна и её окрестности состоят из квадратных районов, образующих правильную сетку. После победы над злыми Волшебницами Запада и Востока добрые Волшебницы Севера и Юга договорились разделить страну на две сферы влияния по следующим правилам:

Каждый из районов страны целиком принадлежит или Северу, или Югу.
Районы, принадлежащие каждой из сторон, образуют связную область (т.е. обойти сферу влияния каждой из волшебниц можно, перемещаясь только между районами, соседними по стороне).
Две сферы влияния имеют одинаковые размеры и форму (т.е. соответствующие фигуры можно перевести друг в друга последовательностью поворотов, сдвигов и отражений).
Каждая из сфер влияния содержит одинаковый по длине участок внешней границы Волшебной страны.
Если есть несколько подходящих разбиений страны, подойдет любое.

Помогите волшебницам разделить Волшебную страну и не поссориться между собой.

В первой строке ввода находятся натуральные числа $N$ и $M$ ( $1<=N,M<=15$ ) — размеры карты. Затем следуют $N$ строк по $M$ символов в каждой — карта страны и окрестностей. Символ '#' обозначает часть Волшебной страны, а символ '.' - окружающую страну пустыню. Гарантируется, что в стране не менее 1 и не более 15 районов, и они образуют связную (по сторонам районов) область, не содержащую фрагментов пустыни внутри себя. Внешняя граница страны - линия, разделяющая '#' и '.'.

Если не существует ни одного способа разделить страну, удовлетворяющего всем условиям, выведите единственную строку Impossible. Иначе выведите $N$ строк по $M$ символов — описание разделения: пустынные районы ('.') должны остаться нетронутыми, районы в сфере влияния Севера отмечены как N, в сфере влияния Юга — как S.

Пример ввода 1

4 5
.#...
.#...
##.#.
.###.

Пример вывода 1

.N...
.N...
NN.S.
.SSS.

Пример ввода 2

2 6
######
##....

Пример вывода 2

Impossible

Пояснение к примеру 1: обе части связны, имеют одинаковую форму и содержат по 9 участков внешней границы страны.
Пояснение к примеру 2: можно разделить страну на 2 связные части одинаковой площади, но они будут иметь разную форму и включать разные по длине участки внешней границы.

29/03/2025	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 4)
29/03/2025	ЦОП: дорешивание Prime Time 2025 (проводит BOGAT) (M)