Given a 2D boolean matrix, the task is to find the number of islands. An island is a group of connected 1s.
For example, the below matrix contains 6 islands
Example:
Input : mat[][] = {{1, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
Output : 6
This is a variation of the standard problem: “Counting the number of connected components in an undirected graph”.
Before we go to the problem, let us understand what is a connected component. A connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path(s), and which is connected to no other vertices outside the subgraph.
For example, the graph shown below has three connected components.
Below is the implementation of the above approach:
PHP
<?php // Program to count islands // in boolean 2D matrix $ROW = 5; $COL = 5; // A function to check if a // given cell (row, col) can // be included in DFS function isSafe(&$M, $row, $col, &$visited) { global $ROW, $COL; // row number is in range, // column number is in // range and value is 1 // and not yet visited return ($row >= 0) && ($row < $ROW) && ($col >= 0) && ($col < $COL) && ($M[$row][$col] && !isset($visited[$row][$col])); } // A utility function to do DFS // for a 2D boolean matrix. It // only considers the 8 neighbours // as adjacent vertices function DFS(&$M, $row, $col, &$visited) { // These arrays are used to // get row and column numbers // of 8 neighbours of a given cell $rowNbr = array(-1, -1, -1, 0, 0, 1, 1, 1); $colNbr = array(-1, 0, 1, -1, 1, -1, 0, 1); // Mark this cell as visited $visited[$row][$col] = true; // Recur for all // connected neighbours for ($k = 0; $k < 8; ++$k) if (isSafe($M, $row + $rowNbr[$k], $col + $colNbr[$k], $visited)) DFS($M, $row + $rowNbr[$k], $col + $colNbr[$k], $visited); } // The main function that returns // count of islands in a given // boolean 2D matrix function countIslands(&$M) { global $ROW, $COL; // Make a bool array to // mark visited cells. // Initially all cells // are unvisited $visited = array(array()); // Initialize count as 0 and // traverse through the all // cells of given matrix $count = 0; for ($i = 0; $i < $ROW; ++$i) for ($j = 0; $j < $COL; ++$j) if ($M[$i][$j] && !isset($visited[$i][$j])) // If a cell with value 1 { // is not visited yet, DFS($M, $i, $j, $visited); // then new island found ++$count; // Visit all cells in this } // island and increment // island count. return $count; } // Driver Code $M = array(array(1, 1, 0, 0, 0), array(0, 1, 0, 0, 1), array(1, 0, 0, 1, 1), array(0, 0, 0, 0, 0), array(1, 0, 1, 0, 1)); echo "Number of islands is: ", countIslands($M); // This code is contributed // by ChitraNayal ?> |
Number of islands is: 5
Time Complexity: O(m x n), where m and n are the numbers of rows and columns of the given matrix respectively.
Auxiliary Space: O(m x n), for creating a visited array of size m * n.
Please refer complete article on Find the number of islands | Set 1 (Using DFS) for more details!
