fork download
copy 
  1. // C++ Program to count islands in boolean 2D matrix 
  2. #include <bits/stdc++.h> 
  3. using namespace std; 
  4.  
  5. #define ROW 5 
  6. #define COL 5 
  7.  
  8. // A function to check if a given 
  9. // cell (row, col) can be included in DFS 
  10. int isSafe(int M[][COL], int row, int col, 
  11. 		bool visited[][COL]) 
  12. { 
  13. 	// row number is in range, column 
  14. 	// number is in range and value is 1 
  15. 	// and not yet visited 
  16. 	return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]); 
  17. } 
  18.  
  19. // A utility function to do DFS for a 
  20. // 2D boolean matrix. It only considers 
  21. // the 8 neighbours as adjacent vertices 
  22. void DFS(int M[][COL], int row, int col, 
  23. 		bool visited[][COL]) 
  24. { 
  25. 	// These arrays are used to get 
  26. 	// row and column numbers of 8 
  27. 	// neighbours of a given cell 
  28. 	static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; 
  29. 	static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; 
  30.  
  31. 	// Mark this cell as visited 
  32. 	visited[row][col] = true; 
  33.  
  34. 	// Recur for all connected neighbours 
  35. 	for (int k = 0; k < 8; ++k) 
  36. 		if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) 
  37. 			DFS(M, row + rowNbr[k], col + colNbr[k], visited); 
  38. } 
  39.  
  40. // The main function that returns 
  41. // count of islands in a given boolean 
  42. // 2D matrix 
  43. int countIslands(int M[][COL]) 
  44. { 
  45. 	// Make a bool array to mark visited cells. 
  46. 	// Initially all cells are unvisited 
  47. 	bool visited[ROW][COL]; 
  48. 	memset(visited, 0, sizeof(visited)); 
  49.  
  50. 	// Initialize count as 0 and 
  51. 	// travese through the all cells of 
  52. 	// given matrix 
  53. 	int count = 0; 
  54. 	for (int i = 0; i < ROW; ++i) 
  55. 		for (int j = 0; j < COL; ++j) 
  56.  
  57. 			// If a cell with value 1 is not 
  58. 			if (M[i][j] && !visited[i][j]) { 
  59. 				// visited yet, then new island found 
  60. 				// Visit all cells in this island. 
  61. 				DFS(M, i, j, visited); 
  62.  
  63. 				// and increment island count 
  64. 				++count; 
  65. 			} 
  66.  
  67. 	return count; 
  68. } 
  69.  
  70. // Driver code 
  71. int main() 
  72. { 
  73. 	int M[][COL] = { { 1, 1, 0, 0, 0 }, 
  74. 					{ 0, 1, 0, 0, 1 }, 
  75. 					{ 1, 0, 0, 1, 1 }, 
  76. 					{ 0, 0, 0, 0, 0 }, 
  77. 					{ 1, 0, 1, 0, 1 } }; 
  78.  
  79. 	cout << "Number of islands is: " << countIslands(M); 
  80.  
  81. 	return 0; 
  82. } 
  83.  
  84. // This is code is contributed by rathbhupendra 
  85.  
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Number of islands is: 5
https://ideone.com/gGCZng
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!