Counting Islands

You are given an \(N \times N\) grid where each cell is either land (L) or water (W). An island is defined as a group of adjacent land cells connected 4-directionally (up, down, left, right). Your task is to count the number of distinct islands in the grid.

Two cells are considered connected if they share a common edge. Use a depth-first search (DFS) or similar method to traverse and mark visited land cells to ensure that each island is only counted once.

inputFormat

The input is read from standard input (stdin) and consists of:

1. An integer \(N\) representing the size of the grid.
2. Followed by \(N\) lines each containing a string of length \(N\) made of characters L (land) and W (water) representing the grid.

For example:

4
LLWW
LWWW
WWLL
WWLL

outputFormat

Output a single integer to standard output (stdout) -- the number of distinct islands in the grid.

For the above sample input, the output should be:

2

4
LLWW
LWWW
WWLL
WWLL

2