PDA

Просмотр полной версии : Разрезание пластины.



Alg
28.07.2008, 16:44
Подскажите как можно решить эту задачу.

С помощью прямоугольной матрицы размером 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

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

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

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

Alg
31.07.2008, 12:55
Разрез не обязательно горизонтален. Например,

00000
00100
01110
01010
00000

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

airyashov
31.07.2008, 13:00
Разрез не обязательно горизонтален. Например,

00000
00100
01110
01010
00000

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

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

00000
00100
01210
02020
00000

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

airyashov
01.08.2008, 07:52
помоему тоже это уже не пластина, рассыпится на отдельные квадраты
определение пластины "пластина, составленная из квадратиков одного размера, примыкающих друг к другу сторонами"

Alg
01.08.2008, 21:33
Нелучший пример, конечно.
Например,
00000
01110
22210
00210
00200