Leetcode.200.Number of Islands

题目

给定一个二维数组, 由'1'和'0'组成, 如果'1'周围都是'0', 计算加1, 最外围默认都是0. 求连通后的'1'的个数.

Input: [['1','1','1'],['0','1','0'],['1','1','1']]
Output: 1
Input: [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]
Output: 3
Input: [['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']]
Output: 1

思路

DFS. 采用递归, 每次对'1'的上下左右进行递归. 遇到'1',则置为0, 遇到'0', 则停止.

void numIslandsRecrution(vector<vector<char>>& grid,int i, int j) {
    if (i < 0 || i >= grid.size() ||
        j < 0 || j >= grid[i].size() ||
        grid[i][j] == '0') {
        return ;
    }

    grid[i][j] = '0';
    numIslandsRecrution(grid,i+1,j);
    numIslandsRecrution(grid,i-1,j);
    numIslandsRecrution(grid,i,j+1);
    numIslandsRecrution(grid,i,j-1);
}

int numIslands(vector<vector<char>>& grid) {
    int res = 0;
    for (int i = 0;i < grid.size();i++) {
        for(int j = 0; j < grid[i].size();j++) {
            if (grid[i][j] == '1') {
                res++;
                numIslandsRecrution(grid, i, j);
            }
        }
    }
    return res;
}

总结

熟悉DFS和BFS的工作原理, 以及常用应用场景.