Developing.ru

Подскажите как можно решить эту задачу.

С помощью прямоугольной матрицы размером m x n задается пластина, составленная из квадратиков одного размера, примыкающих друг к другу сторонами: единичное значение элемента матрицы означает наличие в этом месте квадратика пластины, ноль – пустое место (см.рис.)

Требуется разрезать пластину вдоль границ квадратиков на две равные части либо установить, что такого разрезания не существует. Части считаются равными, если их можно совместить переносом или поворотом в плоскости пластины.

Входные данные

Входной файл input.txt содержит в первой строке пару целых чисел m и n – размеры матрицы (2<=m,n<=20), в каждой из следующих m строк файла содержатся n цифр соответствующей строки матрицы без пробелов.

Выходные данные

В первую строку выходного файла output.txt необходимо вывести “YES”, если требуемое разрезание возможно, и “NO” – в противном случае. Затем, если разрезание возможно, необходимо, начиная со следующей строки, вывести ту же матрицу, оставив в ней «1» на месте квадратиков, относящихся к одной части, и заменив цифрой «2» квадратики, относящиеся к другой части.

http://stud-olymp07.nm.ru/zad_osn.htm

Для начала, можно пересчитать единицы в матрице. Если будет нечётное число, то - однозначно, пластина не делится. Дальше нужно подумать! В приведенной ссылке непонятка - почему 1й вариант делится а второй нет. В обоих случаях требуется зеркальное отображение половинок (хотя об этом в условии ничего не сказано - только поворот и перенос), то есть условию не удовлетворяют оба примера.

В первом случае можно повернуть на 90 градусов против часовой стрелки и совместить параллельным переносом, т. к. на самом деле это квадраты, хотя на рисунке и прямоугольники.

как раз все понятно поворот и перенос, 1 фигура поворот вправо и перенос, 2 - такими действиями не получается

в принципе если заменить " вдоль границ квадратиков" на "вертикальной или горизонтальной линией вдоль границ квадратиков" что как можно доказать является единственным всегда присутствующим при симметрии вариантом разреза то задача реализуется элементарно - перебором

Разрез не обязательно горизонтален. Например,

00000
00100
01110
01010
00000

В этом случае после разреза не горизонтально, а по ломаной, фигуры совместимы.

Alg писал(а):Разрез не обязательно горизонтален. Например,

00000
00100
01110
01010
00000

В этом случае после разреза не горизонтально, а по ломаной, фигуры совместимы.

опишите фигуры 1 и 2, отдельными цифрами

мне тоже не сильно понятно как можно разрезать такую фигуру
кстати у меня написано по горизонтали ИЛИ по вертикали
везде где есть вариант с ломаной есть вариант с прямой изза того что при указанных вариантах совмещения возможно всего 4 варианта поворота

airyashov писал(а):опишите фигуры 1 и 2, отдельными цифрами

00000
00100
01210
02020
00000

Если я это правильно понимаю.

блин действительно можно так разрезать
тогда только рекурсия остается
хотя назвать такое пластиной у меня язык бы не повернулся