Leetcode_200_Number of Islands

[lihe]

Number of Islands

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

方法一：DFS

算法思路：

1. 标记当前搜索位置为已搜索；
2. 按照方向数组的四个方向，拓展四个新位置；
3. 若新位置不在地图内则忽略；
4. 如果新位置未曾到达过且是陆地则继续DFS该位置。

class Solution{
public:
    void DFS(std::vector<std::vector<int>> &mark, std::vector<std::vector<char>> &grid, int x, int y){
        mark[x][y] = 1;
        static const int dx[] = {-1, 1, 0, 0};
        static const int dy[] = {0, 0, -1, 1};
        for(int i = 0; i < 4; i++){
            int newx = dx[i] + x;
            int newy = dy[i] + y;
            if(newx < 0 || newx >= mark.size() || newy < 0 || newy >= mark[newx].size()){
                continue;
            }
            if(mark[newx][newy] == 0 && grid[newx][newy] == '1'){
                DFS(mark, grid, newx, newy);
            }
        }
    }

    int numIslands(std::vector<std::vector<char>> &grid){
        int island_num = 0;
        std::vector<std::vector<int>> mark;
        for(int i = 0; i < grid.size(); i++){
            mark.push_back(std::vector<int>());
            for(int j = 0; j < grid[i].size(); j++){
                mark[i].push_back(0);
            }
        }
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(mark[i][j] == 0 && grid[i][j] == '1'){
                    DFS(mark, grid, i, j);
                    island_num++;
                }
            }
        }
        return island_num;
    }
};

方法二：BFS

算法思路：

1. 设置搜索队列Q，标记mark[i][j] = 1，并将待搜索位置(x, y)push进队列；
2. 只要队列不空，即取队头元素，按照方向数组取四个方向，拓展四个新位置newx, newy；
3. 若新位置不在地图范围内则忽略；
4. 若新位置未曾到达过且是陆地则将新位置push进队列，并标记mark[newx][newy] = 1

class Solution{
public:
    void BFS(std::vector<std::vector<int>> &mark, std::vector<std::vector<char>> &grid, int x, int y){
        static const int dx[] = {-1, 1, 0, 0};
        static const int dy[] = {0, 0, -1, 1};
        std::queue<std::pair<int, int>> Q;
        Q.push(std::make_pair(x, y));
        mark[x][y] = 1;
        while(!Q.empty()){
            x = Q.front().first;
            y = Q.front().second;
            Q.pop();
            for(int i = 0; i < 4; i++){
                int newx = dx[i] + x;
                int newy = dy[i] + y;
                if(newx < 0 || newx >= mark.size() || newy < 0 || newy >= mark[newx].size()){
                    continue;
                }
                if(mark[newx][newy] == 0 && grid[newx][newy] == '1'){
                    Q.push(std::make_pair(newx, newy));
                    mark[newx][newy] = 1;
                }
            }
        }
    }

    int numIslands(std::vector<std::vector<char>> &grid){
        int island_num = 0;
        std::vector<std::vector<int>> mark;
        for(int i = 0; i < grid.size(); i++){
            mark.push_back(std::vector<int>());
            for(int j = 0; j < grid[i].size(); j++){
                mark[i].push_back(0);
            }
        }
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(mark[i][j] == 0 && grid[i][j] == '1'){
                    BFS(mark, grid, i, j);
                    island_num++;
                }
            }
        }
        return island_num;
    }
};