闲着没事(误)开始刷题了，突然觉得自己的算法基础真的是太差了，有时间的时候还是刷刷题目吧。
最近一直用 Python ，所以刷题也继续用了。今天做的都是简单题，简单题中比较难的就刷到一道“岛屿的个数”问题。

题目

描述：
给一个01矩阵，求不同的岛屿的个数。
0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

样例输入：
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]

样例输出：3

总结

总体思路

• 设置一个同大小的标记矩阵 mark ，初始全为 True
• 设置一个计数变量 count
• 按行列遍历 元素为 True 时将对应标记为 False，count+1
• 对于此元素的前后左右进行检查并标记，为 True 时加入列表，按广度优先的方式继续检查直至到达边界
• 继续遍历至结束，注意各种对grid和mark相应的检查

踩到的坑

• 特殊值如 grid = [] or [1]
• grid 并不是方阵，行列数可能不一致
• 对周围元素的检查应当不只是右后，而是上下左右，使用队列可以实现广度优先的检查以便向周围扩展，在编码时注意对 grid 和 mark 的各种检查
• 二维数组的浅拷贝问题，可以看这篇

实现代码

# coding: utf-8
# http://www.lintcode.com/zh-cn/problem/number-of-islands/
# 岛屿的个数

class Solution:
    # @param {boolean[][]} grid a boolean 2D matrix
    # @return {int} an integer
    def numIslands(self, grid):
        # 特殊值检错
        if not grid:
            return 0
        if isinstance(grid[0], bool) or isinstance(grid[0], int):
            return 1 if grid[0] else 0
        # Write your code here
        count = 0   # 计数
        # 行列数
        r, l = len(grid), len(grid[0])
        # 标记初始为True 扩展到的为False不再进行检测
        mark = self._mark(r, l)
        for i in range(r):
            for j in range(l):
                if grid[i][j]:
                    if mark[i][j]:  # 检查标记
                        count += 1
                        mark[i][j] = False  # 有必要？
                        self._expand(i, j, grid, mark)
        return count
                        
    def _mark(self, r, l):
        mark = []
        for i in range(r):
            mark.append([True] * l)
        return mark

    def _expand(self, x, y, grid, mark):
        # 向右向下扩展，广度优先
        t = [(x, y)]
        # 用于检查边界
        r, l = len(grid), len(grid[0])
        while len(t) != 0:
            i, j = t.pop()
            # 左
            if i > 0:
                if mark[i-1][j]:
                    if grid[i-1][j]:
                        mark[i-1][j] = False
                        t.append((i-1, j))
            # 右
            if i < r - 1:
                if mark[i+1][j]:
                    if grid[i+1][j]:
                        mark[i+1][j] = False
                        t.append((i+1, j))

            # 上
            if j > 0:
                if mark[i][j-1]:
                    if grid[i][j-1]:
                        mark[i][j-1] = False
                        t.append((i, j-1))

            # 下
            if j < l - 1:
                if mark[i][j+1]:
                    if grid[i][j+1]:
                        mark[i][j+1] = False
                        t.append((i, j+1))


if __name__ == '__main__':
    g0 = []
    g1 = [1]
    g2 = [0]
    g3 = [[0]]
    g4 = [
        [1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 0, 1],
        [1, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1]]
    g5 = [[1, 1, 0, 0, 0],
          [0, 1, 0, 0, 1], 
          [0, 0, 0, 1, 1], 
          [0, 0, 0, 0, 0], 
          [0, 0, 0, 0, 1]]
    s = Solution()
    for g in [g0, g1, g2, g3, g4, g5]:
        print s.numIslands(g)