Distinct Shapes

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 1G

Author:
Problem types

Given an N \times M 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

1 \le N, M \le 2 \times 10^3

Input Specification

The first line will contain N and M, the number of rows and columns, respectively.

The next N lines will contain M 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

There are no comments at the moment.