Number of Islands - Breadth First Search (BFS)

Problem is here: https://leetcode.com/problems/number-of-islands/description/

Given a 2d grid map of '1's (land) and '0's (water), count 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.
Example 1:
Input:
11110
11010
11000
00000

Output: 1
Example 2:
Input:
11000
11000
00100
00011

Output: 3

I wrote about a similar problem two years back when I was trying to count the number of regions in an image, you can check it out here https://bit.ly/2BiyMy0.
The solution is a simple BFS. Interestingly, the solution is actually linear in the size of the matrix since at most each node is visited only once. Code is below, cheers, A.C.C.


public class Solution
{
 public int NumIslands(char[,] grid)
 {
  int count = 0;

  for (int r = 0; r < grid.GetLength(0); r++)
  {
   for (int c = 0; c < grid.GetLength(1); c++)
   {
    if (grid[r, c] == '1')
    {
     count++;
     Traverse(grid, r, c);
    }
   }
  }

  return count;
 }

 private void Traverse(char[,] grid,
       int row,
       int col)
 {
  Queue queue = new Queue();
  Hashtable visited = new Hashtable();

  queue.Enqueue(row * grid.GetLength(1) + col);
  visited.Add(row * grid.GetLength(1) + col, true);

  while (queue.Count > 0)
  {
   int val = (int)queue.Dequeue();
   row = val / grid.GetLength(1);
   col = val % grid.GetLength(1);
   grid[row, col] = '0';

   for (int r = -1; r <= 1; r += 2)
   {
    if (row + r >= 0 &&
     row + r < grid.GetLength(0) &&
     grid[row + r, col] == '1' &&
     !visited.ContainsKey((row + r) * grid.GetLength(1) + col))
    {
     queue.Enqueue((row + r) * grid.GetLength(1) + col);
     visited.Add((row + r) * grid.GetLength(1) + col, true);
    }
   }
   for (int c = -1; c <= 1; c += 2)
   {
    if (col + c >= 0 &&
     col + c < grid.GetLength(1) &&
     grid[row, col + c] == '1' &&
     !visited.ContainsKey(row * grid.GetLength(1) + col + c))
    {
     queue.Enqueue(row * grid.GetLength(1) + col + c);
     visited.Add(row * grid.GetLength(1) + col + c, true);
    }
   }
  }
 }
}

Comments

  1. Technically any traversal works for this type of problems, which is why most of the time DFS is chosen because then recursion can be used instead of maintaining an explicit stack. But we are not looking for easy ways, so my DFS solution does maintain an explicit stack:

    impl Solution {
    pub fn num_islands(grid: Vec>) -> i32 {
    if grid.is_empty() {
    return 0;
    }
    let mut visited = vec![vec![false; grid[0].len()]; grid.len()];
    const directions: [i32; 5] = [-1, 0, 1, 0, -1];
    let mut islands = 0;
    for x in 0..grid.len() {
    for y in 0..grid[x].len() {
    if visited[x][y] || grid[x][y] != '1' {
    continue
    }
    islands += 1;
    let mut stack = Vec::new();
    stack.push((x, y));
    visited[x][y] = true;
    while !stack.is_empty() {
    let (x, y) = stack.pop().unwrap();
    for (x_dir, y_dir) in directions.iter().zip(directions.iter().skip(1)) {
    let new_x = x as i32 + x_dir;
    let new_y = y as i32 + y_dir;
    if new_x < 0 || new_y < 0 {
    continue
    }
    let new_x = new_x as usize;
    let new_y = new_y as usize;
    if new_x >= grid.len() || new_y >= grid[0].len() || visited[new_x][new_y] || grid[new_x][new_y] != '1' {
    continue
    }
    stack.push((new_x, new_y));
    visited[new_x][new_y] = true;
    }
    }
    }
    }
    islands
    }

    https://gist.github.com/ttsugriy/dc13eec6a9d73738c8d63c34be4370f5

    ReplyDelete
  2. That's true, in this particular case any traversal would do the trick

    ReplyDelete
  3. which coding languge is used here?

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons