Count Islands (Leetcode 16)

Did this one a while ago. “Just” an exercise in DFS, counting connected subgraph or something. A nice enough word-problem for exercising “recognizing” when graphs appear. Ah, that’s a nice topic to consider.

class Solution(object):
    def visited(self, i, j):
        return (i, j) in self.seenSet
    def mark(self, i, j):
        self.seenSet.add((i, j))
    def neighbors(self, i, j):
        ns = []
        if i > 0:
            ns.append((i-1, j))
        if j > 0:
            ns.append((i, j-1))
        if i < (len(self.grid) - 1):
            ns.append((i+1, j))
        if j < (len(self.grid[0]) - 1):
            ns.append((i, j+1))
        return ns
    def markIsland(self, i, j):
        assert(self.grid[i][j] == '1')
        assert(not self.visited(i, j))
        toMark = [(i, j)]
        while toMark:
            i, j = toMark.pop()
            if self.visited(i, j):
                continue
            self.mark(i, j)
            for n in self.neighbors(i, j):
                a, b = n
                if self.grid[a][b] == '1':
                    if not self.visited(a, b):
                        toMark.append(n)
                        
    def numIslands(self, grid):
        self.seenSet = set([])
        self.grid = grid
        islandCount = 0
        for i in range(len(grid)): # for each row
            for j in range(len(grid[i])): # for each column
                if grid[i][j] == "0":
                    continue
                if self.visited(i, j):
                    continue
                self.markIsland(i, j)
                islandCount+=1
        return islandCount

Leave a Reply