| | | |
|
Шахматная доска
Двумерные массивы
Клеточная геометрия
Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.
Входные данные
Сначала вводится число N (1 ≤ N ≤ 64) – количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.
Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3
1 1
1 2
2 1 |
8 |
Вырезан уголок из трех клеток. Сумма длин его сторон равна 8. |
| 2 |
1
8 8 |
4 |
Вырезана одна клетка. Ее периметр равен 4. |
| |
![]()
|
|
Восстанови многоугольник
Клеточная геометрия
Двумерные массивы
Вася нарисовал на клетчатой бумаге многоугольник, все стороны которого проходят по линиям сетки. После этого в каждой клетке он написал число, равное количеству сторон данной клетки, которые принадлежат сторонам многоугольника. Затем он стер многоугольник так, что остался листок бумаги, в каждой клетке которого написано число.
Восстановите нарисованный Васей многоугольник.
Входные данные
В первой строке входных данных содержатся два натуральных числа: Y - количество строк и X - количество столбцов листа (3 <= Y <= 1000, 3 <= X <= 1000). В каждой из следующих Y строк задается по X целых неотрицательных чисел, не превосходящих 4. Ни одна из сторон многоугольника не проходит по границе листа бумаги.
Выходные данные
Выведите искомый многоугольник в следующем формате.
Выходные данные должны содержать Y строк по 2X-1 символов в каждой (по одному символу на клетку и линию между клетками).
В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.
Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.
| |
![]()
|
|
Поиск прямоугольников
Динамическое программирование на таблицах
Клеточная геометрия
На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.
Получившуюся ситуацию записали в таблицу чисел (каждой клетке поля соответствует клетка таблицы). Если клетка поля не закрыта прямоугольником, то в соответствующую клетку таблицы записали число 0. Если же клетка закрыта одним или несколькими прямоугольниками, то в соответствующую клетку таблицы записали число, соответствующее номеру самого верхнего прямоугольника, закрывающего эту клетку.
По содержимому таблицы требуется определить положение и размеры прямоугольников.
Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.
| 0 |
2 |
2 |
2 |
2 |
| 0 |
2 |
2 |
2 |
2 |
| 1 |
1 |
2 |
2 |
2 |
| 1 |
1 |
0 |
0 |
0 |
Входные данные
В первой строке входного файла записаны целые числа N, M, K (1≤N≤200, 1≤M≤200, 1≤K≤255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.
Выходные данные
В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.
Оси координат устроены следующим образом: начало координат находится в нижнем левом углу поля, а оси координат направлены вдоль сторон поля (ось Ox — вдоль нижней стороны, а ось Oy — вдоль левой стороны). Клетки поля имеют размер 1x1. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N). Заметьте, что вы должны вывести координаты углов прямоугольников (как точек) в этой системе координат, а не координаты угловых клеток, покрытых прямоугольниками.
| |
![]()
|
