Где Уолли
Знакомы ли вы с популярной серией детских книг "Где Уолли"? В каждой книге множество иллюстраций с сотнями людей, и читателям предлагается найти персонажа по имени Уолли среди толпы.
Мы можем рассматривать "Где Уолли" как задачу по сопоставлению двумерных графических образцов. Необходимо найти фигуру Уолли на изображении. Было бы интересно создать компьютерную программу для решения этой задачи, но это непросто, так как Уолли может немного отличаться на разных картинках. Мы отказываемся от этой идеи и предлагаем более простую задачу по сопоставлению графических образцов.
Вам даны изображение и образец. Оба представлены в виде прямоугольных матриц битов (образец всегда квадратный). 0 обозначает белый цвет, а 1 — черный. Ваша задача — подсчитать количество вхождений образца в изображение, то есть количество квадратов в изображении, которые точно совпадают с образцом. Также учитываются образцы, которые появляются в поворотах на кратные 90 градусов и/или в зеркальном отображении.
Входные данные
Входные данные состоят из последовательности наборов данных в следующем формате.
w h p данные изображения данные образца
Первая строка каждого набора данных содержит три положительных целых числа: w, h и p. w — это ширина изображения, h — высота изображения, оба измеряются в битах. p — это ширина и высота образца, который всегда квадратный. Можно предположить, что 1 ≤ w ≤ 1000, 1 ≤ h ≤ 1000, и 1 ≤ p ≤ 100.
Следующие h строк содержат изображение. Каждая строка состоит из w/6 (что равно (w+5)/6) символов и представляет горизонтальную линию изображения. Каждый символ кодирует шесть битов этой линии в формате BASE64. Правила кодирования приведены в таблице. Самый значимый бит соответствует самому левому биту на изображении. Последний символ может содержать несколько битов за пределами ширины изображения; эти биты следует игнорировать.
Последние p строк содержат образец. Каждая строка состоит из p/6 символов и закодирована так же, как и изображение.
Строка с тремя нулями указывает на конец ввода. Общий размер входных данных не превышает двух мегабайт.
Выходные данные
Для каждого набора данных на входе выведите одну строку, содержащую количество совпадающих квадратов в изображении. Строка вывода не должна содержать лишних символов.
Два или более совпадающих квадрата могут частично перекрываться, и в таком случае они учитываются отдельно. Однако один квадрат не учитывается дважды, даже если он совпадает как с оригинальным образцом, так и с его поворотом.