Областная олимпиада по информатике, 2009-2010 учебный год

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

Ограничение по времени:

2 sec.

Ограничение по памяти:

64 MB

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

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

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

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

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

Пример:

Вход:

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

 Ответ:

2