Count the Islands

You are given a 2D grid representing a map where each cell is either land ('X') or water ('O'). An island is a group of adjacent lands connected horizontally or vertically. Your task is to count the number of islands present in the grid.

The problem can be modeled using the graph traversal technique (e.g. DFS or BFS) to identify connected components.

In mathematical terms, if we denote the grid as a matrix \( A \) of dimensions \( m \times n \), then an island is defined by a set of indices \( \{(i,j)\} \) such that \( A_{i,j} = 'X' \) and for any two land cells in the same island, there exists a sequence of adjacent cells connecting them. The boundaries of connectivity are given by the adjacency relation: \( (i,j) \) is adjacent to \( (i-1,j), (i+1,j), (i,j-1), (i,j+1) \).

inputFormat

The first line of input contains two integers \( m \) and \( n \) (the number of rows and columns respectively).

This is followed by \( m \) lines, each containing a string of length \( n \) composed of characters 'X' and 'O', representing the grid.

outputFormat

Output a single integer, which is the number of islands found in the grid.

4 4
XOOO
XOXO
OOXX
OXOX

3