算法

(DFS) $O(nm)$

本题是floodfill的板题，只需搜出全为'1'的连通块即可。

C++ 代码

class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int cnt = 0;

    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        if (n == 0) return 0;
        int m = grid[0].size();
        vector<vector<int>> color(n, vector<int>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1' && !color[i][j]) {
                    cnt++;
                    floodFill(grid, color, i, j);
                }
            }
        }
        return cnt;
    }

    void floodFill(vector<vector<char>> &grid, vector<vector<int>> &color, int x, int y) {
        color[x][y] = cnt;
        int n = grid.size();
        int m = grid[0].size();
        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) {
                if (!color[xx][yy] && grid[xx][yy] == '1') {
                    floodFill(grid, color, xx, yy);
                }
            }
        }
    }
};