Областная олимпиада по информатике 2010 года за 10 класс | Казахстанские олимпиады

Задача E. Фигуры

Ограничение по времени Ограничение по памяти
2 sec. 64 MB

Назовем фигурой множество клеток, связанных по стороне. Будем считать фигуры одинаковыми, если их можно совместить поворотами и перемещениями. На листе бумаги в клетку нарисовано множество фигур, посчитайте, сколько из них различных.

Формат входного файла

Первая строка содержит два целых числа N и М (1≤ N, М ≤ 100) – размер листа в клетках. Следующие N строк содержат по М символов каждая. Возможные символы: ’.’, если данная клетка пустая, или ’#’, если она является частью какой-то фигуры.

Формат выходного файла

Выходной файл должен содержать одно целое число – количество различных фигур.

Примеры

Вход

10 10
.......... 
.#...#.... 
.###.#.... 
....##.... 
.......... 
..###..... 
....#..... 
.......#.. 
.......#.. 
.......##.

Выход

2