Number of Islands - Breadth First Search (BFS)
Problem is here: https://leetcode.com/problems/number-of-islands/description/
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.
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);
}
}
}
}
}
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:
ReplyDeleteimpl 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
That's true, in this particular case any traversal would do the trick
ReplyDeletewhich coding languge is used here?
ReplyDelete