Episode 24 – Depth-First Search (DFS)

The Code Snippets Podcast
The Code Snippets Podcast
Episode 24 - Depth-First Search (DFS)
/

Today i solve the problem “Number of Islands”

grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
  ]



  def num_islands(grid)
    islands = 0
    return islands if grid.empty?

    grid.each_with_index do |row, i|
        row.each_with_index do |col, j|
            if grid[i][j] == '1'
                dfs(grid, i, j)
                islands += 1
            end
        end
    end

    islands
end

def dfs(grid, i, j)
    return if i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'

    grid[i][j] = '0' 
    dfs(grid, i + 1, j)
    dfs(grid, i - 1, j)
    dfs(grid, i, j + 1)
    dfs(grid, i, j - 1)
end

puts num_islands(grid)