8.岛问题

岛问题

【题目】

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？

【例子】

0 0 1 0 1 0

1 1 1 0 1 0

1 0 0 1 0 0

0 0 0 0 0 0

这个矩阵中有三个岛。

【进阶】

如何设计一个并行算法解决这个问题。

【思路】有一个infect函数，会把连城一片的1全变成2。深度优先遍历或者宽度优先遍历这个矩阵，遇到是1的元素则调用infect函数，最后调用了多少次infect函数就有多少个岛。

【代码】

int countIslands(vector<vector<int>> &matrix) {
    if (matrix.empty()) {
        return 0;
    }
    int m = matrix.size();
    int n = matrix[0].size();
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                ++res;
                infect(matrix, i, j, m, n);
            }
        }
    }
    return res;
}
//infect函数，会把连城一片的1全变成2
void infect(vector<vector<int>> &vec, int i, int j, int m, int n) {
    if (i < 0 || i >= m || j < 0 || j >= n || vec[i][j] != 1) {
        return;
    }
    //i,j没越界，并且当前位置值都是1
    vec[i][j] = 2;
    infect(vec, i + 1, j, m, n);
    infect(vec, i - 1, j, m, n);
    infect(vec, i, j + 1, m, n);
    infect(vec, i, j - 1, m, n);
}