Number of Islands

Solution

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        vector<vector<bool> > visited(m, vector<bool>(n, false));
        int count = 0;
        for(int i = 0; i<m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j]=='1' && !visited[i][j]) {
                    foundIsland(grid, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }
void foundIsland(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j) {
        if(grid[i][j]=='0' || visited[i][j]) {
            return;
        }
        int m = grid.size();
        int n = grid[0].size();
        visited[i][j] = true;
        if(i>0) {
            foundIsland(grid, visited, i-1, j);
        }
        if(i < m-1) {
            foundIsland(grid, visited, i+1, j);
        }

        if(j>0) {
            foundIsland(grid, visited, i, j-1);
        }
        if(j < n-1) {
            foundIsland(grid, visited, i, j+1);
        }
    }
};

Follow up

what if it is one dimension?

int numIsland(vector<char> line) {
    int cnt =0;
    if(line.empty()) return cnt;
    for(int i=0; i<line.size(); i++) {
        while(line[i] == '0') {
            i++;
        }
        if(i < line.size()) {
            cnt++;
        } else {
            break;
        }
        while(line[i] == '1') {
            i++;
        }
    }
    return cnt;
}