Подскажите как можно решить эту задачу.
С помощью прямоугольной матрицы размером 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
В этом случае после разреза не горизонтально, а по ломаной, фигуры совместимы.
00000
00100
01110
01010
00000
В этом случае после разреза не горизонтально, а по ломаной, фигуры совместимы.
Alg писал(а):Разрез не обязательно горизонтален. Например,
00000
00100
01110
01010
00000
В этом случае после разреза не горизонтально, а по ломаной, фигуры совместимы.
опишите фигуры 1 и 2, отдельными цифрами
мне тоже не сильно понятно как можно разрезать такую фигуру
кстати у меня написано по горизонтали ИЛИ по вертикали
везде где есть вариант с ломаной есть вариант с прямой изза того что при указанных вариантах совмещения возможно всего 4 варианта поворота
кстати у меня написано по горизонтали ИЛИ по вертикали
везде где есть вариант с ломаной есть вариант с прямой изза того что при указанных вариантах совмещения возможно всего 4 варианта поворота
airyashov писал(а):опишите фигуры 1 и 2, отдельными цифрами
00000
00100
01210
02020
00000
Если я это правильно понимаю.
блин действительно можно так разрезать
тогда только рекурсия остается
хотя назвать такое пластиной у меня язык бы не повернулся
тогда только рекурсия остается
хотя назвать такое пластиной у меня язык бы не повернулся