注：本文摘自唐巧博客，方便以后查阅。请谅解
今天这篇是算法系列面试题的最后一篇了，之后的面试题我将继续选择 iOS 开发相关的一些问题来讨论。
问题
在一个地图中，找出一共有多少个岛屿。
我们用一个二维数组表示这个地图，地图中的 1 表示陆地，0 表示水域。一个岛屿是指由上下左右相连的陆地，并且被水域包围的区域。
你可以假设地图的四周都是水域。
例一：
11110
11010
11000
00000
以上地图，一共有 1 个岛屿。
例二：
11000
11000
00100
00011
以上地图，一共有 3 个岛屿。
答案
这是 LeetCode 上的 第 200 题，我们可以用一种被称为「种子填充」(floodfill)的办法来解决此题。
具体的做法是：
1、遍历整个地图，找到一个未被标记过的，值为 1 的坐标。
2、从这个坐标开始，从上下左右四个方向，标记相邻的 1 。
3、把这些相邻的坐标，都标记下来，递归的进行标记，以便把相邻的相邻块也能标记上。
4、待标记全部完成之后，将岛屿的计数 +1。
5、回到第 1 步。如果第 1 步无法找到未标记的坐标，则结束。
虽然思路简单，但是实现起来代码量也不算小。这里有一些小技巧：
1、我们可以将上下左右四个方向的偏移量保存在数组中，这样在计算位置的时候，写起来更简单一些。
2、递归的标记过程可以用深度优先搜索（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
}
}
Swift 的参数默认是不能修改值的，但是如果是 C++ 语言的话，我们可以直接在地图上做标记。因为地图只有 0 和 1 两种值，我们可以用 2 表示「标记过的陆地」，这样就省略了额外的标记数组。以下是我写的一个 C++ 的示例程序：
class Solution {
public:
void fillLands(vector<vector<char>>& grid, int px, int py) {
int movex[] = {0, 0, 1, -1};
int movey[] = {-1, 1, 0, 0};
queue<pair<int, int>> q;
q.push(make_pair(px, py));
grid[px][py] = '2';
while (!q.empty()) {
pair<int, int> item = q.front();
q.pop();
int tox, toy;
for (int i = 0; i < 4; ++i) {
tox = item.first + movex[i];
toy = item.second + movey[i];
if (tox >= 0 && tox < grid.size()
&& toy >=0 && toy < grid[0].size()
&& grid[tox][toy] == '1') {
grid[tox][toy] = '2';
q.push(make_pair(tox, toy));
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
fillLands(grid, i, j);
ans++;
}
}
}
return ans;
}
};
微信公众号编辑器对代码排版支持很差，更好的代码排版，请看：https://gist.github.com/tangqiaoboy/5a5e5beb2cd020ed1f803958a8f2c318
这类题目有相当多的变种，希望大家能够掌握。
