LeetCode200.岛屿的个数

题目链接：LeetCode200

题解

dfs做法，遇到1，就进入infect函数，将1及其周围是1的全部”感染“成2

代码

class Solution {
    int n,m;
    public int numIslands(char[][] grid) {
        int res = 0;
        if(grid.length == 0) 
            return res;
        n = grid.length;
        m = grid[0].length;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(grid[i][j] == '1') {
                    res++;
                    infect(grid,i,j);
                }
            }
        }
        return res;
    }
    public void infect(char[][] grid,int x,int y) {
        if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != '1')
            return;
        grid[x][y] = '2';
        infect(grid,x + 1,y);
        infect(grid,x - 1,y);
        infect(grid,x,y + 1);
        infect(grid,x,y - 1);
    }
}

还有一种做法是利用并查集，本身这道题的标签也是并查集，可能别人也希望你用并查集来做吧。如果一个点为1，那这个点和它四周为1的点同属一个集合，如果一个点为0，那么把它的父结点置为-1，最后统计出现不为-1的不同数字的个数即可

class Solution {
public:
    vector<int> set;
    int find(int x) {
        if(x!=set[x]) set[x] = find(set[x]);
        return set[x];
    }
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        for(int i = 0;i < m * n; i++) set.push_back(i);
        for(int i = 0; i < m ; i++) {
            for(int j = 0; j < n; j++) {
                int x = i * n + j;
                if(grid[i][j] == '0') {
                    set[x] = -1;
                    continue;
                }
                if(i != 0 && grid[i-1][j] == '1') {
                    int y = (i - 1) * n + j;
                    set[find(x)] = find(y);
                }
                if(j != 0 && grid[i][j-1] == '1') {
                    int y = i * n + j -1;
                    set[find(x)] = find(y);
                }
            }
        }
        int res = 0;
        unordered_map<int, int> mp;
        for(int i = 0 ;i < m * n ; i++) {
            if(set[i] == -1) continue;
            int y = find(i);
            if(!mp[y]) {
                res++;
                mp[y] = 1;
            }
        }
        return res;
    }
};