Задача 13.
Представьте себе, что в тетрадке Вы зарисовали на листе какое-то количество клеточек и получили клеточную фигуру.
Сколько осей симметрии имеет заданная клеточная фигура.
Пояснение :
1) Задается S - число тестов. Для каждого теста задаются NI размер фигуры по вертикали, NJ - размер фигуры по горизонтали (NI<101, NJ<81) и сама фигура в виде NI строк из пробелов и единиц по NJ символов в каждой строке.
2) Числа S, NI, NJ занимают при вводе по три позиции.
Пример .
Входные данные :
2 ( количество тестов )
2 ( размер 1-ой фигуры по вертикали )
4 ( размер 1-ой фигуры по горизонтали )
1111
1 1
3 ( размер 2-ой фигуры по вертикали )
5 ( размер 2-ой фигуры по горизонтали )
11111
111
111
Выходные сообщения:
1-АЯ ФИГУРА ИМЕЕТ 1 ОСЕЙ СИММЕТРИИ
2-АЯ ФИГУРА ИМЕЕТ 0 ОСЕЙ СИММЕТРИИ
|
Решение задачи 13.
У клеточной фигуры (представьте себе, что в тетрадке Вы зарисовали на листе какое-то количество клеточек) могут быть следующие оси симметрии - горизонтальная, вертикальная и идущие под углом 45 и -45 градусов (т.е. 4 оси симметрии - как у квадрата). При любых других осях клетки листа при отображении не перейдут в клетки. Оси могут проходить как через центр какой-то клетки, так и по стороне. Например, фигуры
***
*** и ***
имеют по 2 оси симметрии - горизонтальную и вертикальную, а фигура * - все 4 оси симметрии.
Вводим систему координат таким образом, что каждая зарисованная клетка представляется точкой с целочисленными координатами.
Находим вероятный центр симметрии фигуры(имеющий координаты
((Xmax + Xmin)/2, (Ymax+Ymin)/2), где Xmax, Ymax, Xmin и Ymin соответственно максимальные и минимальные иксовые и игрековые координаты точек в заданной нами системе координат:
Xmax = max{Xi} ; Ymax = max{Yi},
Xmin = min{Xi} ; Ymin = min{Yi} ).
Если у фигуры есть ось симметрии, то она проходит через этот вероятный центр симметрии фигуры
Рассматриваем 4 возможных оси симметрии, проходящие через этот центр. Определяем, является ли фигура симметричной относительно каждой из осей. (Для удобства этот центр можно считать началом системы координат. При симметрии относительно горизонтальной (вертикальной) оси каждой клетке фигуры (x,y) должна соответствовать клетка с такой
же иксовой (игрековой) координатой, но с обратной по знаку другой координатой, т.е. (x,-y) (соответственно, для вертикальной оси (-x,y)). При симметрии относительно оси с наклоном 45 (-45) градусов каждой клетке (x,y) фигуры должна соответствовать клетка с координатой (y,x) (соответственно (-y,-x)).
|
