Daa-/Number Of Islands.cpp at main · encryptau/Daa- · 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//{ Driver Code Starts
// Initial Template for C++

#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
// User function Template for C++
class Solution {
  public:
   void solve(vector<vector<int>> &store,vector<vector<bool>> &vis, int row, int col, int n, int m){


        if(row<0 || col<0 || row>=n || col>=m || vis[row][col]==true|| store[row][col] ==0){

            return;

        }

        vis[row][col]=true;

        solve(store,vis,row-1,col,n,m);

        solve(store,vis,row+1,col,n,m);

        solve(store,vis,row,col-1,n,m);

        solve(store,vis,row,col+1,n,m);


    }

    vector<int> numOfIslands(int n, int m, vector<vector<int>> &operators) {

        // code here


        vector<vector<int>> store(n,vector<int> (m,0));

        vector<vector<bool>> vis(n,vector<bool> (m,false));

        vector<int> ans;


        for(auto it: operators){

            int row = it[0];

            int col = it[1];

            store[row][col]=1;

            int count=0;

            for(int i=0;i<n;i++){

                for(int j=0;j<m;j++){

                    if(store[i][j]==1 && vis[i][j] == false){

                        solve(store,vis,i,j,n,m);

                        count++;

                    }


                }


            }

            vector<vector<bool>> naya(n,vector<bool> (m,false));

            vis=naya;

            ans.push_back(count);

        }

        return ans;

    }
};


//{ Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n,m,k; cin>>n>>m>>k;
        vector<vector<int>> a;

        for(int i=0; i<k; i++){
            vector<int> temp;
            for(int j=0; j<2; j++){
                int x; cin>>x;
                temp.push_back(x);
            }
            a.push_back(temp);
        }

        Solution obj;
        vector<int> res = obj.numOfIslands(n,m,a);

        for(auto x : res)cout<<x<<" ";
        cout<<"\n";
    }
}

// } Driver Code Ends