Number of islands problem

Question

Accepted Answer

The number of islands problem involves counting the number of connected islands in a grid.

An island is a group of connected 1s in a grid of 0s and 1s.
Use depth-first search or breadth-first search to traverse the grid and count the islands.
Keep track of visited cells to avoid counting the same island multiple times.

Accepted Answer

# Program to count islands in boolean 2D matrix

class Graph:

def __init__(self, row, col, g):

self.ROW = row

self.COL = col

self.graph = g

# A function to check if a given cell

# (row, col) can be included in DFS

def isSafe(self, i, j, visited):

# row number is in range, column number

# is in range and value is 1

# and not yet visited

return (i >= 0 and i < self.ROW and

j >= 0 and j < self.COL and

not visited[i][j] and self.graph[i][j])

# A utility function to do DFS for a 2D

# boolean matrix. It only considers

# the 8 neighbours as adjacent vertices

def DFS(self, i, j, visited):

# These arrays are used to get row and

# column numbers of 8 neighbours

# of a given cell

rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1];

colNbr = [-1, 0, 1, -1, 1, -1, 0, 1];

# Mark this cell as visited

visited[i][j] = True

# Recur for all connected neighbours

for k in range(8):

if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):

self.DFS(i + rowNbr[k], j + colNbr[k], visited)

# The main function that returns

# count of islands in a given boolean

# 2D matrix

def countIslands(self):

# Make a bool array to mark visited cells.

# Initially all cells are unvisited

visited = [[False for j in range(self.COL)]for i in range(self.ROW)]

# Initialize count as 0 and traverse

# through the all cells of

# given matrix

count = 0

for i in range(self.ROW):

for j in range(self.COL):

# If a cell with value 1 is not visited yet,

# then new island found

if visited[i][j] == False and self.graph[i][j] == 1:

# Visit all cells in this island

# and increment island count

self.DFS(i, j, visited)

count += 1

return count

graph = [[1, 1, 0, 0, 0],

[0, 1, 0, 0, 1],

[1, 0, 0, 1, 1],

[0, 0, 0, 0, 0],

[1, 0, 1, 0, 1]]

row = len(graph)

col = len(graph[0])

g = Graph(row, col, graph)

print ("Number of islands is:")

print (g.countIslands())

# This code is contributed by Neelam Yadav

Number of islands problem

Top Microsoft Corporation Intern interview questions & answers

Popular interview questions of Intern

Top HR questions asked in Microsoft Corporation Intern