正文
iOS 面试题（14）：计算有多少个岛屿
原创
2017-02-08
唐巧
iOS开发by唐巧
今天这篇是算法系列面试题的最后一篇了，之后的面试题我将继续选择 iOS 开发相关的一些问题来讨论。
问题
在一个地图中，找出一共有多少个岛屿。
我们用一个二维数组表示这个地图，地图中的 1
表示陆地，0
表示水域。一个岛屿是指由上下左右相连的陆地，并且被水域包围的区域。
你可以假设地图的四周都是水域。
例一：
11110110101100000000
以上地图，一共有 1 个岛屿。
例二：
11000110000010000011
以上地图，一共有 3 个岛屿。
答案
这是 LeetCode 上的 第 200 题，我们可以用一种被称为「种子填充」(floodfill)的办法来解决此题。
具体的做法是：
遍历整个地图，找到一个未被标记过的，值为 1
的坐标。
从这个坐标开始，从上下左右四个方向，标记相邻的 1
。
把这些相邻的坐标，都标记下来，递归的进行标记，以便把相邻的相邻块也能标记上。
待标记全部完成之后，将岛屿的计数 +1
。
回到第 1 步。如果第 1 步无法找到未标记的坐标，则结束。
虽然思路简单，但是实现起来代码量也不算小。这里有一些小技巧：
我们可以将上下左右四个方向的偏移量保存在数组中，这样在计算位置的时候，写起来更简单一些。
递归的标记过程可以用深度优先搜索（DFS）或者宽度优先搜索（BFS）。
以下是完整的参考代码：
private class Solution { private var flag: [[Int]] private var answer: Int private var movex : [Int] { return [-1, 1, 0, 0] } private var movey : [Int] { return [0, 0, -1, 1] } init() { flag =
[Int]
answer = 0 } func dfs(_ grid: [[Character]] ,_ x: Int,_ y: Int) { for i in 0..<4 { let tox = x + movex[i] let toy = y + movey[i] if tox >= 0 && tox < grid.count && toy >= 0 && toy < grid[0].count && grid[tox][toy] == "1" && flag[tox][toy] == 0 { flag[tox][toy] = 1 dfs(grid, tox, toy) } } } func numIslands(_ grid: [[Character]]) -> Int { answer = 0 flag = grid.map { $0.map { _ in return 0 }} for i in 0..<grid.count { for j in 0..<grid[i].count { if grid[i][j] == "1" && flag[i][j] == 0 { flag[i][j] = 1 // print("find in (i), (j)") dfs(grid, i, j) answer += 1 } } } return answer }}
