class Solution {
public:
    int n, m;
    bool visited[309][309];
    vector<vector<char> > v;
    const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    void dfs(int x, int y) {
        visited[x][y] = true;
        for(int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (!visited[nx][ny] && v[nx][ny] == '1') {
                dfs(nx, ny);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        v = grid;
        n = grid.size(), m = grid[0].size();

        int ret = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    ret++;
                    dfs(i, j);
                }
            }
        }
        return ret;
    }
};