问题：在一个地图中，找出一共有多少个岛屿。
我们用一个二维数组表示这个地图，地图中的 1 表示陆地，0 表示水域。一个岛屿是指由上下左右相连的陆地，并且被水域包围的区域。
你可以假设地图的四周都是水域。
例一：一共有 1 个岛屿。
11110
11010
11000
00000
例二：一共有 3 个岛屿。
11000
11000
00100
00011
答案:这是 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..
for j in 0..
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>& grid, int px, int py) {
int movex[] = {0, 0, 1, -1};
int movey[] = {-1, 1, 0, 0};
queue> q;
q.push(make_pair(px, py));
grid[px][py] = '2';
while (!q.empty()) {
pair 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>& 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;
}
};
网友评论