Counting Distinct Islands

You are given a grid consisting of land and water cells. The land cells are represented by the character L and water cells by the character W. Two land cells are connected if they are adjacent horizontally or vertically (diagonals are not considered connected). An island is a maximal group of connected land cells. Your task is to count the number of distinct islands in the grid.

Example:

Input:
4
LWLWL
LWLWL
WWWWW
WWLLW
Output:
4

In the example above, the grid has 4 distinct islands. Use depth-first search (DFS) or a similar technique to solve this problem.

inputFormat

The first line contains an integer N representing the number of rows in the grid. The following N lines each contain a string of equal length consisting of characters L and W.

outputFormat

Output a single integer—the number of distinct islands in the grid.## sample

3
LWW
WLW
WWL

3