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