岛屿的个数
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000 输出: 1
示例 2:
输入:
11000
11000
00100
00011 输出: 3
我的思想：
输入是一个二维数组，"0" 代表是水 "1"代表是陆地 （注意里面存的是字符串，很坑 我调了半天才发现）
从左上角(0, 0)开始 遍历所有位置 一直到右下角 (m, n)， 这个过程中
如果发现当前位置是"1"， 先把这个位置标记为查询过，
然后递归查看当前位置的上下左右四个位置，把是"1"的标记遍历过，再查看这个位置的上下左右
实际上是一个循环 套了一个递归来实现。
当发现一个陆地 就计数器自增1 然后和这个陆地相连的所有陆地都标记为已经查找过 小技巧：
遍历图的时候，边界位置要留意，左边没有左侧，上边没有上侧，右边没有右侧，下边没有下侧，
可以写分支判断如果是边界就不遍历外侧。
我选择的办法是，在图的外侧增加一圈"0", 相当于扩大了整个图，
这样在递归陆地的过程中会节省了判断，并且不用考虑超出范围的问题。 python代码：
class Solution:
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
# 如果是空图 返回没有陆地
if not grid:
return 0
# 把原图改变一下 四周加上一圈"0" 防止出界 方便遍历
w, h = len(grid[0]), len(grid)
new_grid = [["" for i in range(w + 2)]]
for g in grid:
new_grid.append([""] + g + [""])
new_grid.append(["" for i in range(w + 2)]) num = 0 # 记录陆地数量 # 遍历除了周围的"0" 中间的部分
for i in range(1, h+1):
for j in range(1, w+1):
if new_grid[i][j] == "": # 如果是陆地 就进入深度遍历
num += 1
self.deep_search(i, j, new_grid) return num def deep_search(self, i, j, grid):
"""如果当前是陆地，把当前结点标记遍历过，并分别看左右上下四个位置"""
if grid[i][j] == "":
return
grid[i][j] = ""
self.deep_search(i-1,j,grid)
self.deep_search(i,j-1,grid)
self.deep_search(i,j+1,grid)
self.deep_search(i+1,j,grid)