# Count number of islands where every island is row-wise and column-wise separated

Given a rectangular matrix which has only two possible values ‘X’ and ‘O’. The values ‘X’ always appear in form of rectangular islands and these islands are always row-wise and column-wise separated by at least one line of ‘O’s. Note that islands can only be diagonally adjacent. Count the number of islands in the given matrix.

Examples:

```mat[M][N] =  {{'O', 'O', 'O'},
{'X', 'X', 'O'},
{'X', 'X', 'O'},
{'O', 'O', 'X'},
{'O', 'O', 'X'},
{'X', 'X', 'O'}
};
Output: Number of islands is 3

mat[M][N] =  {{'X', 'O', 'O', 'O', 'O', 'O'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'O', 'O', 'O', 'O', 'O', 'O'},
{'X', 'X', 'X', 'O', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'X'},
{'O', 'O', 'O', 'O', 'X', 'X'},
};
Output: Number of islands is 4
```

We strongly recommend to minimize your browser and try this yourself first.

The idea is to count all top-leftmost corners of given matrix. We can check if a ‘X’ is top left or not by checking following conditions.
1) A ‘X’ is top of rectangle if the cell just above it is a ‘O’
2) A ‘X’ is leftmost of rectangle if the cell just left of it is a ‘O’

Note that we must check for both conditions as there may be more than one top cells and more than one leftmost cells in a rectangular island. Below is the implementation of above idea.

## C/C++

 `// A C++ program to count the number of rectangular ` `// islands where every island is separated by a line ` `#include ` `using` `namespace` `std; ` ` `  `// Size of given matrix is M X N ` `#define M 6 ` `#define N 3 ` ` `  `// This function takes a matrix of 'X' and 'O' ` `// and returns the number of rectangular islands ` `// of 'X' where no two islands are row-wise or ` `// column-wise adjacent, the islands may be diagonaly ` `// adjacent ` `int` `countIslands(``int` `mat[][N]) ` `{ ` `    ``int` `count = 0; ``// Initialize result ` ` `  `    ``// Traverse the input matrix ` `    ``for` `(``int` `i=0; i

/div>

## Java

 `// A Java program to count the number of rectangular ` `// islands where every island is separated by a line ` `import` `java.io.*; ` ` `  `class` `islands  ` `{ ` `    ``// This function takes a matrix of 'X' and 'O' ` `    ``// and returns the number of rectangular islands ` `    ``// of 'X' where no two islands are row-wise or ` `    ``// column-wise adjacent, the islands may be diagonaly ` `    ``// adjacent ` `    ``static` `int` `countIslands(``int` `mat[][], ``int` `m, ``int` `n) ` `    ``{ ` `        ``// Initialize result ` `        ``int` `count = ``0``;  ` ` `  `        ``// Traverse the input matrix ` `        ``for` `(``int` `i=``0``; i

## Python3

 `# A Python3 program to count the number  ` `# of rectangular islands where every  ` `# island is separated by a line ` ` `  `# Size of given matrix is M X N ` `M ``=` `6` `N ``=` `3` ` `  `# This function takes a matrix of 'X' and 'O' ` `# and returns the number of rectangular  ` `# islands of 'X' where no two islands are  ` `# row-wise or column-wise adjacent, the islands  ` `# may be diagonaly adjacent ` `def` `countIslands(mat): ` ` `  `    ``count ``=` `0``; ``# Initialize result ` ` `  `    ``# Traverse the input matrix ` `    ``for` `i ``in` `range` `(``0``, M): ` `     `  `        ``for` `j ``in` `range``(``0``, N): ` `         `  `            ``# If current cell is 'X', then check ` `            ``# whether this is top-leftmost of a ` `            ``# rectangle. If yes, then increment count ` `            ``if` `(mat[i][j] ``=``=` `'X'``): ` `             `  `                ``if` `((i ``=``=` `0` `or` `mat[i ``-` `1``][j] ``=``=` `'O'``) ``and` `                    ``(j ``=``=` `0` `or` `mat[i][j ``-` `1``] ``=``=` `'O'``)): ` `                    ``count ``=` `count ``+` `1` `             `  `    ``return` `count ` ` `  `# Driver Code ` `mat ``=` `[[``'O'``, ``'O'``, ``'O'``], ` `       ``[``'X'``, ``'X'``, ``'O'``], ` `       ``[``'X'``, ``'X'``, ``'O'``], ` `       ``[``'O'``, ``'O'``, ``'X'``], ` `       ``[``'O'``, ``'O'``, ``'X'``], ` `       ``[``'X'``, ``'X'``, ``'O'``]] ` `                 `  `print``(``"Number of rectangular islands is"``,  ` `                       ``countIslands(mat)) ` ` `  `# This code is contributed by iAyushRaj `

## C#

 `// A C# program to count the number of rectangular  ` `// islands where every island is separated by  ` `// a line ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// This function takes a matrix of 'X' and 'O' ` `    ``// and returns the number of rectangular  ` `    ``// islands of 'X' where no two islands are ` `    ``// row-wise or column-wise adjacent, the ` `    ``// islands may be diagonaly adjacent ` `    ``static` `int` `countIslands(``int` `[,]mat, ``int` `m, ``int` `n) ` `    ``{ ` `         `  `        ``// Initialize result ` `        ``int` `count = 0;  ` ` `  `        ``// Traverse the input matrix ` `        ``for` `(``int` `i = 0; i < m; i++) ` `        ``{ ` `            ``for` `(``int` `j = 0; j < n; j++) ` `            ``{ ` `                ``// If current cell is 'X', then check ` `                ``// whether this is top-leftmost of a ` `                ``// rectangle. If yes, then increment ` `                ``// count ` `                ``if` `(mat[i,j] == ``'X'``) ` `                ``{ ` `                    ``if` `((i == 0 || mat[i-1,j] == ``'O'``) && ` `                        ``(j == 0 || mat[i,j-1] == ``'O'``)) ` `                        ``count++; ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``return` `count; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `         `  `        ``// Size of given matrix is m X n ` `        ``int` `m = 6; ` `        ``int` `n = 3; ` `        ``int` `[,]mat = { {``'O'``, ``'O'``, ``'O'``}, ` `                       ``{``'X'``, ``'X'``, ``'O'``}, ` `                       ``{``'X'``, ``'X'``, ``'O'``}, ` `                       ``{``'O'``, ``'O'``, ``'X'``}, ` `                       ``{``'O'``, ``'O'``, ``'X'``}, ` `                       ``{``'X'``, ``'X'``, ``'O'``} ` `                    ``}; ` `        ``Console.WriteLine(``"Number of rectangular "` `         ``+ ``"islands is: "` `+ countIslands(mat, m, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

## PHP

 ` `

Output:

`Number of rectangular islands is 3`

Time complexity of this solution is O(MN).

Matrix Matrix