123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Function to determine if the cell
is valid (within grid's boundaries) */
bool isValid(int i, int j, int n, int m) {
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
void bfs(int i, int j, vector<vector<bool>>& vis,
vector<vector<char>>& grid) {
// Mark the node as visited
vis[i][j] = true;
// Queue required for BFS traversal
queue<pair<int, int>> q;
// push the node in queue
q.push({i, j});
// Dimensions of grid
int n = grid.size();
int m = grid[0].size();
// Until the queue becomes empty
while (!q.empty()) {
// Get the cell from queue
pair<int, int> cell = q.front();
q.pop();
// Determine its row & column
int row = cell.first;
int col = cell.second;
// Traverse the 8 neighbours
for (int delRow = -1; delRow <= 1; delRow++) {
for (int delCol = -1; delCol <= 1; delCol++) {
// Coordinates of new cell
int newRow = row + delRow;
int newCol = col + delCol;
/* Check if the new cell is valid,
unvisited, and a land cell */
if (isValid(newRow, newCol, n, m)
&& grid[newRow][newCol] == '1'
&& !vis[newRow][newCol]) {
// Mark the node as visited
vis[newRow][newCol] = true;
// Push new cell in queue
q.push({newRow, newCol});
}
}
}
}
}
public:
// Function to find the number of islands in given grid
int numIslands(vector<vector<char>>& grid) {
// Size of the grid
int n = grid.size();
int m = grid[0].size();
// Visited array
vector<vector<bool>> vis(n, vector<bool>(m, false));
// To store the count of islands
int count = 0;
// Traverse the grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
/* If not visited and is a land,
start a new traversal */
if (!vis[i][j] && grid[i][j] == '1') {
count++;
bfs(i, j, vis, grid);
}
}
}
return count;
}
};
int main() {
vector<vector<char>> grid = {
{'1', '1', '1', '0', '1'},
{'1', '0', '0', '0', '0'},
{'1', '1', '1', '0', '1'},
{'0', '0', '0', '1', '1'}
};
// Creating an instance of Solution class
Solution sol;
/* Function call to find the
number of islands in given grid */
int ans = sol.numIslands(grid);
cout << "The total islands in given grids are: " << ans << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
import java.util.*;
class Solution {
/* Function to determine if the cell
is valid (within grid's boundaries) */
private boolean isValid(int i, int j,
int n, int m) {
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
private void bfs(int i, int j, boolean[][] vis,
char[][] grid) {
// mark it visited
vis[i][j] = true;
// Queue required for BFS traversal
Queue<int[]> q = new LinkedList<>();
// push the node in queue
q.add(new int[]{i, j});
// Dimensions of grid
int n = grid.length;
int m = grid[0].length;
// Until the queue becomes empty
while (!q.isEmpty()) {
// Get the cell from queue
int[] cell = q.poll();
// Determine it's row & column
int row = cell[0];
int col = cell[1];
// Traverse the 8 neighbours
for (int delRow = -1; delRow <= 1; delRow++) {
for (int delCol = -1; delCol <= 1; delCol++) {
// Coordinates of new cell
int newRow = row + delRow;
int newCol = col + delCol;
/* Check if the new cell is valid,
unvisited, and a land cell */
if (isValid(newRow, newCol, n, m)
&& grid[newRow][newCol] == '1'
&& !vis[newRow][newCol]) {
// Mark the node as visited
vis[newRow][newCol] = true;
// Push new cell in queue
q.add(new int[]{newRow, newCol});
}
}
}
}
}
// Function to find the number of islands in given grid
public int numIslands(char[][] grid) {
// Size of the grid
int n = grid.length;
int m = grid[0].length;
// Visited array
boolean[][] vis = new boolean[n][m];
// To store the count of islands
int count = 0;
// Traverse the grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
/* If not visited and is a land,
start a new traversal */
if (!vis[i][j] && grid[i][j] == '1') {
count++;
bfs(i, j, vis, grid);
}
}
}
return count;
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '1', '0', '1'},
{'1', '0', '0', '0', '0'},
{'1', '1', '1', '0', '1'},
{'0', '0', '0', '1', '1'}
};
// Creating an instance of Solution class
Solution sol = new Solution();
/* Function call to find the
number of islands in given grid */
int ans = sol.numIslands(grid);
System.out.println("The total islands in given grids are: " + ans);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
from collections import deque
class Solution:
# Function to determine if the cell is
# valid (within grid's boundaries)
def isValid(self, i, j, n, m):
if i < 0 or i >= n:
return False
if j < 0 or j >= m:
return False
# Return true if cell is valid
return True
def bfs(self, i, j, vis, grid):
# mark it visited
vis[i][j] = True
# Queue required for BFS traversal
q = deque()
# push the node in queue
q.append((i, j))
# Dimensions of grid
n = len(grid)
m = len(grid[0])
# Until the queue becomes empty
while q:
# Get the cell from queue
row, col = q.popleft()
# Traverse the 8 neighbours
for delRow in range(-1, 2):
for delCol in range(-1, 2):
# Coordinates of new cell
newRow = row + delRow
newCol = col + delCol
# Check if the new cell is valid,
# unvisited, and a land cell
if (
self.isValid(newRow, newCol, n, m) and
grid[newRow][newCol] == '1' and
not vis[newRow][newCol]
):
# Mark the node as visited
vis[newRow][newCol] = True
# Push new cell in queue
q.append((newRow, newCol))
# Function to find the number of islands in given grid
def numIslands(self, grid):
# Size of the grid
n = len(grid)
m = len(grid[0])
# Visited array
vis = [[False for _ in range(m)] for _ in range(n)]
# To store the count of islands
count = 0
# Traverse the grid
for i in range(n):
for j in range(m):
# If not visited and is a land,
# start a new traversal
if not vis[i][j] and grid[i][j] == '1':
count += 1
self.bfs(i, j, vis, grid)
return count
if __name__ == "__main__":
grid = [
['1', '1', '1', '0', '1'],
['1', '0', '0', '0', '0'],
['1', '1', '1', '0', '1'],
['0', '0', '0', '1', '1']
]
# Creating an instance of Solution class
sol = Solution()
# Function call to find the number of islands in given grid
ans = sol.numIslands(grid)
print("The total islands in given grids are:", ans)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
class Solution {
/* Function to determine if the cell
is valid (within grid's boundaries) */
isValid(i, j, n, m) {
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
bfs(i, j, vis, grid) {
// mark it visited
vis[i][j] = true;
// Queue required for BFS traversal
let q = [];
// push the node in queue
q.push([i, j]);
// Dimensions of grid
let n = grid.length;
let m = grid[0].length;
// Until the queue becomes empty
while (q.length > 0) {
// Get the cell from queue
let cell = q.shift();
// Determine it's row & column
let row = cell[0];
let col = cell[1];
// Traverse the 8 neighbours
for (let delRow = -1; delRow <= 1; delRow++) {
for (let delCol = -1; delCol <= 1; delCol++) {
// Coordinates of new cell
let newRow = row + delRow;
let newCol = col + delCol;
/* Check if the new cell is valid,
unvisited, and a land cell*/
if (this.isValid(newRow, newCol, n, m)
&& grid[newRow][newCol] == '1'
&& !vis[newRow][newCol]) {
// Mark the node as visited
vis[newRow][newCol] = true;
// Push new cell in queue
q.push([newRow, newCol]);
}
}
}
}
}
/* Function to find the number
of islands in given grid*/
numIslands(grid) {
// Size of the grid
let n = grid.length;
let m = grid[0].length;
// Visited array
let vis = Array.from({ length: n }, () => Array(m).fill(false));
// To store the count of islands
let count = 0;
// Traverse the grid
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
/* If not visited and is a
land, start a new traversal */
if (!vis[i][j] && grid[i][j] == '1') {
count++;
this.bfs(i, j, vis, grid);
}
}
}
return count;
}
}
// Main function to test the solution
(function() {
let grid = [
['1', '1', '1', '0', '1'],
['1', '0', '0', '0', '0'],
['1', '1', '1', '0', '1'],
['0', '0', '0', '1', '1']
];
/* Creating an instance of
Solution class */
let sol = new Solution();
/* Function call to find the
number of islands in given grid*/
let ans = sol.numIslands(grid);
console.log("The total islands in given grids are:", ans);
})();
