Island Counting with BFS

Problem

Count the islands in a grid of string 1 land cells and string 0 water cells, where an island is a group of land cells connected horizontally or vertically.

Scan every cell and run BFS from each unvisited land cell, marking the whole island as visited. Return 0 for an empty grid.

Hint

Each BFS flood fill removes exactly one whole island from future consideration.

Test cases

case 1

in: [[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]]

expected: 1

case 2

in: [[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]]

expected: 3

case 3

in: [[["0"]]]

expected: 0

case 4

in: [[["1"]]]

expected: 1

case 5

in: [[]]

expected: 0

Starter codePython

def count_islands(grid):
    # Your code here
    pass

5 test cases · run your code against them in the editor