Задача: 711. Number of Distinct Islands II
Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.
Пример:
Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1
👨💻 Алгоритм:
1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.
2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.
3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.
😎 Решение:
class Solution {
public:
int numDistinctIslands2(vector<vector<int>>& grid) {
unordered_set<string> uniqueIslands;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
vector<pair<int, int>> shape;
dfs(grid, i, j, i, j, shape);
uniqueIslands.insert(normalize(shape));
}
}
}
return uniqueIslands.size();
}
private:
void dfs(vector<vector<int>>& grid, int i, int j, int baseI, int baseJ, vector<pair<int, int>>& shape) {
if (i < 0 || i >= grid.size() || j < 0од Задача
:
711. Number ofgrid[i][j]
== 0) {
return;
}
grid[i][j] = 0;
shape.emplace_back(i - baseI, j - baseJ);
dfs(grid, i + 1, j, baseI, baseJ, shape);
dfs(grid, i - 1, j, baseI, baseJ, shape);
dfs(grid, i, j + 1, baseI, baseJ, shape);
dfs(grid, i, j - 1, baseI, baseJ, shape);
}
string normalize(vector<pair<int, int>>& shape) {
vector<vector<pair<int, int>>> shapes(8);
for (auto& p : shape) {
int x = p.first, y = p.second;
shapes[0].emplace_back(x, y);
shapes[1].emplace_back(x, -y);
shapes[2].emplace_back(-x, y);
shapes[3].emplace_back(-x, -y);
shapes[4].emplace_back(y, x);
shapes[5].emplace_back(y, -x);
shapes[6].emplace_back(-y, x);
shapes[7].emplace_back(-y, -x);
}
for (auto& s : shapes) {
sort(s.begin(), s.end());
}
string minShape = to_string(shapes[0][0].first) + "," + to_string(shapes[0][0].second);
for (auto& s : shapes) {
string sStr;
for (auto& p : s) {
sStr += to_string(p.first) + "," + to_string(p.second) + ";";
}
minShape = min(minShape, sStr);
}
return minShape;
}
};👉Новости 👉База вопросов