Given an grid of water (.
) or land (#
), determine the number of distinct island shapes.
An island is a group of land cells that all share a side.
An island is not distinct from another island if it has the same number of land cells and can perfectly overlap the island (if shifted horizontally some cells and vertically some cells) without having any land cells on water.
Constraints
Input Specification
The first line will contain and , the number of rows and columns, respectively.
The next lines will contain characters, the sea map.
Output Specification
Output the number of distinct island shapes that are present on the map.
Sample Input 1
6 5
#.#..
#.#..
...##
...##
###..
###..
Sample Output 1
3
Sample Input 2
4 3
###
...
.#.
###
Sample Output 2
2
Comments