Running speed difference

disinct_islands_opt.cpp

#include <bits/stdc++.h>

#define ll long long
#define vec vector

#define MAX_INF 0x3f3f3f3
#define MIN_INF 0xc0c0c0c0

using namespace std;

class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0;
        unordered_set<string> islands;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    string island;
                    distinct(grid, i, j, i, j, island);
                    islands.insert(island);
                }
            }
        }
        return islands.size();
    }
private:
    void distinct(vector<vector<int>>& grid, int i, int j, int r, int c, string& island) {
        int m = grid.size(), n = grid[0].size();
        if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c]) {
            grid[r][c] = 0;
            island += to_string(r - i) + to_string(c - j);
            distinct(grid, i, j, r - 1, c, island);
            distinct(grid, i, j, r + 1, c, island);
            distinct(grid, i, j, r, c - 1, island);
            distinct(grid, i, j, r, c + 1, island);
        }
    }
};

int main() {
    int n, k, ans = 0;

    cout << ans << endl;
}

/// This takes around 65ms and 30mb memory

distinct_islands.cpp

#include <bits/stdc++.h>

#define ll long long
#define vec vector

#define MAX_INF 0x3f3f3f3
#define MIN_INF 0xc0c0c0c0

using namespace std;

// 00 01 10
// 03 04
// 30 31
// 24 33 34
//
// 00 01 10
// 00 01 00 01
// 00 10 11
//
//

typedef pair<int, int> cell;


map<cell, bool> seen;

set<vector<vector<int>>> islands;

vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void dfs(vector<vector<int>>& grid, int r0, int c0, cell ce, vector<vector<int>>& acc) {
    if (ce.first < 0 or ce.second < 0 or ce.first >= grid.size() or ce.second >= grid[0].size() or seen[ce]) return;
    if (grid[ce.first][ce.second] == 0) return;

    seen[ce] = true;
    acc.push_back(vector<int>(ce.first-r0, ce.second-c0));

    for (auto &dir: dirs) {
        dfs(grid, r0, c0, cell(ce.first+dir[0], ce.second+dir[1]), acc);
    }
}

int solve(vector<vector<int>>& grid) {
    int count;
    islands.clear();
    seen.clear();

    for (int i = 0, n = grid.size(); i < n; ++i) {
        for (int j = 0, m = grid[0].size(); j < m; ++j) {
            vector<vector<int>> acc;
            dfs(grid, i, j, cell(i, j), acc);

            if (!acc.empty()) islands.insert(acc);
        }
    }

    return islands.size();
}

int main() {
    int n, k, ans = 0;

    vector<vector<int>> grid = {
        {1,1,0,1,1},
        {1,0,0,0,0},
        {0,0,0,0,1},
        {1,1,0,1,1}
    };

    ans = solve(grid);

    grid = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,0,1,1},
        {0,0,0,1,1}
    };

    ans = {
        {1,1,0,1,1},[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]

    ans = solve(grid);
    cout << ans << endl;
}


// This takes around 245seconds with around 50mb memory