leetCode/lintCode/algorithms/cpp/_860_NumberOfDistinctIslands.cpp at master · shivamacs/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
53
54
55
56
57
58
59
60
61
62
63
/* Leetcode Premium -> 694. Number of Distinct Islands
   Lintcode -> 860. Number of Distinct Islands
*/
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>>& grid, int x, int y, string d, string& path) {
    if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0)
        return;

    if(grid[x][y] == 2) {
        path += "B";
        return;
    }

    grid[x][y] = 2;
    path += d;

    dfs(grid, x, y + 1, "R", path);
    dfs(grid, x + 1, y, "D", path);
    dfs(grid, x, y - 1, "L", path);
    dfs(grid, x - 1, y, "U", path);
}

int numberofDistinctIslands(vector<vector<int>> &grid) {
    int islands = 0;
    string path = "";
    unordered_set<string> distinct;

    for(int i = 0; i < grid.size(); i++) {
        for(int j = 0; j < grid[i].size(); j++) {
            if(grid[i][j] == 1) {
                path = "X";
                dfs(grid, i, j, "", path);

                if(distinct.find(path) == distinct.end()) {
                    distinct.insert(path);
                    islands++;
                }
            }
        }
    }

    return islands;
}

int main()
{
    int n, m;

    cout<<"Enter grid dimensions: ";
    cin>>n>>m;

    vector<vector<int>> grid(n, vector<int> (m));

    cout<<"Enter values row-wise (0 - water, 1 - land): "<<endl;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++)
            cin>>grid[i][j];
    }

    cout<<"Number of distinct islands: "<<numberofDistinctIslands(grid)<<endl;
}