explain the functionality used in the below program. explain all the functions and algorithem used in this program. #include #include using namespace std; #define ROW 5 #define COL 5 // A function to check if a given // cell (row, col) can be included in DFS int isSafe(int M[][COL], int row, int col, bool visited[][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] && !visited[row][col]); } // A utility function to do DFS for a // 2D boolean matrix. It only considers // the 8 neighbours as adjacent vertices void DFS(int M[][COL], int row, int col, bool visited[][COL]) { // These arrays are used to get // row and column numbers of 8 // neighbours of a given cell static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; // Mark this cell as visited visited[row][col] = true; // Recur for all connected neighbours for (int 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 int countIslands(int M[][COL]) { // Make a bool array to mark visited cells. // Initially all cells are unvisited bool visited[ROW][COL]; memset(visited, 0, sizeof(visited)); // Initialize count as 0 and // travese through the all cells of // given matrix int count = 0; for (int i = 0; i < ROW; ++i) for (int j = 0; j < COL; ++j) // If a cell with value 1 is not if (M[i][j] && !visited[i][j]) { // visited yet, then new island found // Visit all cells in this island. DFS(M, i, j, visited); // and increment island count ++count; } return count; } // Driver code int main() { int M[][COL] = { { 1, 1, 0, 0, 0 }, { 0, 1, 0, 0, 1 }, { 1, 0, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 1, 0, 1, 1, 0 } }; cout << "Number of islands is: " << countIslands(M); return 0; }
explain the functionality used in the below program. explain all the functions and algorithem used in this program.
#include<iostream>
#include<string.h>
using namespace std;
#define ROW 5
#define COL 5
// A function to check if a given
// cell (row, col) can be included in DFS
int isSafe(int M[][COL], int row, int col,
bool visited[][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] &&
!visited[row][col]);
}
// A utility function to do DFS for a
// 2D boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(int M[][COL], int row, int col,
bool visited[][COL])
{
// These arrays are used to get
// row and column numbers of 8
// neighbours of a given cell
static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int 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
int countIslands(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
// Initialize count as 0 and
// travese through the all cells of
// given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
// If a cell with value 1 is not
if (M[i][j] && !visited[i][j]) {
// visited yet, then new island found
// Visit all cells in this island.
DFS(M, i, j, visited);
// and increment island count
++count;
}
return count;
}
// Driver code
int main()
{
int M[][COL] = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 1, 0 } };
cout << "Number of islands is: " << countIslands(M);
return 0;
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
