class Solution {
public:
    int dx[4] = {1, -1, 0,0};
    int dy[4] = {0,0,1,-1};
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())return 0;

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

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

    }

    void dfs(int i,int j,vector<vector<char>>&g)
    {
        g[i][j]='0';

        for(int k=0;k<4;k++)
        {
            int nx = i+dx[k];
            int ny = j+dy[k];
            if(nx<0 || ny <0 || nx>=g.size() || ny>=g[0].size() || g[nx][ny]=='0')continue;
            dfs(nx, ny, g);
        }


    }
};