Leetcode/3619_Count_Islands__with_Total_Value_Divisible_By_K.cpp at 240e526a712ab7d3c8ef26c25bf5305fe44b1de3 · SjxSubham/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        int m=grid.size();
        int n=grid[0].size();
        int cnt=0;
        vector<vector<bool>> visited(m,vector<bool> (n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //cout<<i<<" "<<j<<" "<<visited[i][j]<<'\n';
                if(!(visited[i][j])&&grid[i][j]>0){
                    long long sum=0;
                    int a=i;
                    int b=j;
                    dfs(grid,visited,a,b,sum,m,n);
                    //cout<<sum<<" "<<grid[i][j]<<" "<<i<<" "<<j<<"\n";
                    if(sum%k==0){
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
    void dfs(vector<vector<int>>& grid, vector<vector<bool>> &visited, int &x,int &y, long long &sum, int m, int n){
        sum+=grid[x][y];
        //cout<<grid[x][y]<<" "<<x<<" "<<y<<" ";
        visited[x][y]=true;
        if(x<m-1){
           int l=x+1;
           if(grid[l][y]!=0&&!visited[l][y])
            dfs(grid,visited,l,y,sum,m,n);
        }
        if(y<n-1){
            int h=y+1;
            if(grid[x][h]!=0&&!visited[x][h])
            dfs(grid,visited,x,h,sum,m,n);
        }
        if(x>0){
            int a=x-1;
            if(grid[a][y]>0 &&!visited[a][y])
             dfs(grid,visited,a,y,sum,m,n);
        }
        if(y>0){
            int b=y-1;
            if(grid[x][b]>0 &&!visited[x][b])
            dfs(grid,visited,x,b,sum,m,n);
        }

    }

};