I didn't think about DFS or BFS when encountered this problem. I came up with this solution. The run time is O(n^2) average with n being the number of cells in the grid.

I've learned a lot by reading other's solutions. My idea here may be interesting. Explanation is in the comments.

```
class Solution(object):
# Steps:
# 1. Flood fill. Scan row by row.
# If cell value is 1, add cell coordinates to "Bag of lands"
# Check immediate sorroundings of the cell, see if they are already in bag of lands.
# If yes, do not increment island count. Add this land to that lsland's list of lands
# If no, increment island count by 1
# If this check is "yes" for two islands, we know they need to merge.
# 3. Output result
#
# The bag of lslands will be a dictionary eventually of size at most 2n (n is number of cells).
# It contains keys as labels of islands(1,2,3,4...), the value of such key is list of land
# coordiantes. And it also contains keys as tuples as coordinates, the value of such key is
# the island label.
def checkLandAdjacency(self, cell, bag):
# Check cells in adjacent 2 directions, left and up. Only need to check 2
# because we assume we scan from top to down, from left to right.
# Besides, We don't care grid dimensions here, since invalid cells won't
# be in the bag anyways.
i, j = cell
labelLeft = -1
labelUp = -1
hasAdjacentLand = False
hasDifferentAdjacentLand = False
if (i, j-1) in bag: # Left
hasAdjacentLand = True
labelLeft = bag[(i,j-1)]
if (i-1, j) in bag: # Up
hasAdjacentLand = True
labelUp = bag[(i-1, j)]
if labelUp != -1 and labelLeft != -1 and labelUp != labelLeft:
# We encountered two different islands!
hasDifferentAdjacentLand = True
# Note that we prefer the cell in the leftwards direction, for consistency.
return (hasAdjacentLand, hasDifferentAdjacentLand, labelLeft, labelUp)
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if len(grid) == 0:
return 0
bag = {}
maxLabel = 0 # The label of current island.
for i in range(len(grid)):
for j in range(len(grid[i])):
cell = grid[i][j]
if cell == "1":
hasAdjacentLand, hasDifferentAdjacentLand, labelLeft, labelUp \
= self.checkLandAdjacency((i,j), bag)
label = labelLeft if labelLeft >= 0 else labelUp
if hasAdjacentLand:
# Add this cell to the bag. Two keys
bag[(i,j)] = label
bag[label].append((i,j))
else:
# This might be a new island.
maxLabel += 1
bag[(i,j)] = maxLabel
bag[maxLabel] = [(i,j)]
if hasDifferentAdjacentLand:
# Merge the two islands. Merge left to up.
landsLeft = bag[labelLeft]
for ll in landsLeft:
bag[ll] = labelUp
bag[labelUp].append(ll)
bag.pop(labelLeft)
count = 0
for key in bag:
if type(key) is int:
count += 1
return count
```