Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Question
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Solution
This problem can be solved using Depth-First Search (DFS) algorithm. Here are the steps:
-
Initialize a variable
countto 0 to keep track of the number of islands. -
Loop through each cell in the grid. If the cell value is '1', increment
countby 1 and call the DFS function on that cell. -
In the DFS function, first check if the current cell is within the grid boundaries and if it is a '1'. If not, return from the function.
-
Mark the current cell as '0' to indicate that it has been visited.
-
Call the DFS function recursively on all four adjacent cells (up, down, left, right).
-
After the DFS function is done, it will have visited all cells in the current island. Return to the main function and continue with the next cell in the grid.
-
After all cells in the grid have been visited,
countwill hold the number of islands. Returncount.
Here is a Python code snippet that implements the above steps:
def numIslands(grid):
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
DFS(grid, i, j)
count += 1
return count
def DFS(grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
DFS(grid, i+1, j)
DFS(grid, i-1, j)
DFS(grid, i, j+1)
DFS(grid, i, j-1)
This code will return the number of islands in the given 2D
Similar Questions
200. Number of IslandsMediumTopicsCompaniesGiven an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.Return the number of closed islands.Input FormatThe First line contains two integers denoting the value of n and mThe Next N lines contains M integers denoting the elements of the matrix.Constraints1 <= grid.length, grid[0].length <= 1000 <= grid[i][j] <=1Output FormatPrint a integer which is the answer to the question.Sample Input 03 50 0 1 0 00 1 0 1 00 1 1 1 0Sample Output 01Sample Input 13 41 0 1 1 1 1 1 1 1 1 1 1 Sample Output 10
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
200. Number of Islands
You are given a 2D matrix grid of size m x n. You need to check if each cell grid[i][j] is:Equal to the cell below it, i.e. grid[i][j] == grid[i + 1][j] (if it exists).Different from the cell to its right, i.e. grid[i][j] != grid[i][j + 1] (if it exists).Return true if all the cells satisfy these conditions, otherwise, return false. Example 1:Input: grid = [[1,0,2],[1,0,2]]Output: trueExplanation:All the cells in the grid satisfy the conditions.Example 2:Input: grid = [[1,1,1],[0,0,0]]Output: falseExplanation:All cells in the first row are equal.Example 3:Input: grid = [[1],[2],[3]]Output: falseExplanation:Cells in the first column have different values. Constraints:1 <= n, m <= 100 <= grid[i][j] <= 9
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.