LeetCode HOT100 - 岛屿数量

第一时间想到的倒是并查集搞这种合并的形式

但是并没有道理，因为我们是要看相当于有哪几个连通块

用搜索的方式去做，每找到一个 1 就把它能走到的 1 都走了，并标记为访问过

class Solution {
public:
    int numIslands(vector<vector<char>>& a) {
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1}; 
        int n = a.size();
        int m = a[0].size();
        vector<vector<int>> color(n, vector<int>(m, -1));
        int tot = 0;
        auto dfs = [&](auto self, int x, int y) -> void{
            if (a[x][y] == '0') {
                return;
            }
            color[x][y] = tot;
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && color[xx][yy] == -1) self(self, xx, yy);
            }
        };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == '1' && color[i][j] == -1) {
                    ++tot;
                    dfs(dfs, i, j);
                }
            }
        }
        return tot;
    }
};

不过实际上没必要使用 color 数组，直接在原数组上修改记录下 tot 的数值就可以，思路上倒都差不多