# brain dead, no hash, straightforward solution

• A straightforward solution, note isReflection() and is90()

``````class Solution {
struct point {
int x, y;
point(int x_, int y_) :x(x_), y(y_) {;}
bool operator<(const point& other) const {
if (other.y == y) {
return other.x < x;
}
return other.y < y;
}

bool operator!=(const point& other) const {
return x != other.x || y != other.y; // or !(*this < other) && !(*this > other)
}

bool operator==(const point& other) const {
return !(*this != other);
}
};

int n, m;

const vector<int> dx {-1, 0, 1, 0};
const vector<int> dy {0, 1, 0, -1};

point getNext(int i, int x, int y) {
return point{x + dx[i], y + dy[i]};
}

bool inBound(point& p) {
return p.x >= 0 && p.x < n && p.y >= 0 && p.y <m;
}

void collector(vector<point>& points, int x, int y, vector<vector<int>>& grid) {
deque<point> q;
q.emplace_back(x, y);
int minx = x, miny = y;
while(!q.empty()) {
auto top = q.front();
q.pop_front();
points.push_back(top);
for (int i = 0; i < 4; ++i) {
auto next = getNext(i, top.x, top.y);
if (inBound(next) && grid[next.x][next.y]) {
grid[next.x][next.y] = 0;
q.emplace_back(next.x, next.y);
minx = min(minx, next.x);
miny = min(miny, next.y);
}
}
}
for (auto& p: points) {
p.x -= minx;
p.y -= miny;
}
sort(points.begin(), points.end());
}

bool isReflection(vector<point>& l, vector<point> r) {
if (l.size() != r.size()) return false;
int minx = INT_MAX;
for (int i = 0; i < r.size(); ++i) {
r[i].x = -r[i].x;
minx = min(minx, r[i].x);
}

for (int i = 0; i < r.size(); ++i) {
r[i].x -= minx;
}

sort(r.begin(), r.end());
return l == r;
}

// rotate r
bool is90(vector<point>& l, vector<point>& r) {
if (l.size() != r.size()) return false;
int minx = INT_MAX, miny = INT_MAX;
for (int i = 0; i < r.size(); ++i) {
int oldx = r[i].x, oldy = r[i].y;
r[i].x = oldy; r[i].y = -oldx;
minx = min(minx, r[i].x);
miny = min(miny, r[i].y);
}

for (int i = 0; i < r.size(); ++i) {
r[i].x -= minx; r[i].y -= miny;
}

sort(r.begin(), r.end());
return l == r;
}

public:
int numDistinctIslands2(vector<vector<int>>& grid) {
vector<vector<point>> islands;
unordered_set<int> index;
n = grid.size();
if (0 == n) return 0;
m = grid[0].size();
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (1 == grid[x][y]) {
grid[x][y] = 0;
islands.emplace_back();
index.insert(islands.size() - 1);
collector(islands.back(), x, y, grid);
}
}
}
auto cur = index.begin();
while (cur != index.end()) {
auto itor = std::next(cur);
while (itor != index.end()) {
bool eq = false;
for (auto r : {90, 180, 270, 360}) {
if (is90(islands[*cur], islands[*itor]) ||
isReflection(islands[*cur], islands[*itor])) {
itor = index.erase(itor);
eq = true;
break;
}
}

if (!eq) {
itor++;
}
}
cur++;
}
return index.size();
}
};
``````

Post here for reference, but a hashed version would be much better in terms of runtime though.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.