class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())return 0;

        int n = (int)grid.size();
        int m = grid[0].size();

        vector<vector<int>>visit(n, vector<int>(m, 0));
        int ans = 0;

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

        return ans;


    }

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

        visit[i][j] = 1;

        dfs(i, j-1, visit, g);
        dfs(i, j+1, visit, g);
        dfs(i-1, j, visit, g);
        dfs(i+1, j, visit, g);
    }
};