Leetcode 200 Number of Islands 并查集

triplebee

发布于 2018-01-12 14:46:54

1.1K0

发布于 2018-01-12 14:46:54

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110110101100000000

Answer: 1

Example 2:

11000110000010000011

Answer: 3

相邻方向的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;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-03-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

count