Số lượng đảo khác nhau trong C++

Giới thiệu

Cho lưới nhị phân 2D. Đảo là nhóm các ô 1 liên kết 4 hướng (trên/dưới/trái/phải). Hai đảo được coi là giống nhau nếu có thể dịch chuyển (không xoay/lật) để trùng khớp. Đếm số đảo riêng biệt.

Thuật toán: DFS + Ký hiệu hình dạng (Shape Signature)

DFS từ mỗi ô 1 chưa thăm, ghi lại đường đi dưới dạng chuỗi ký tự hướng (ví dụ: 'r','l','d','u','b' cho backtrack). Chuỗi này đại diện cho hình dạng đảo bất biến dưới phép dịch chuyển. Lưu vào set để đếm distinct.

Cài đặt C++

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

class Solution {
    void dfs(int x, int y, vector<vector<int>>& grid, string& path, char dir) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 0) return;
        grid[x][y] = 0; // mark visited
        path += dir;
        dfs(x+1, y, grid, path, 'r');
        dfs(x-1, y, grid, path, 'l');
        dfs(x, y+1, grid, path, 'd');
        dfs(x, y-1, grid, path, 'u');
        path += 'b'; // backtrack marker
    }
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        set<string> shapes;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    string path = "";
                    dfs(i, j, grid, path, 's'); // 's' = start
                    shapes.insert(path);
                }
            }
        }
        return shapes.size();
    }
};

int main() {
    Solution ob;
    vector<vector<int>> grid = {
        {1,1,0,1,1},
        {1,0,0,0,0},
        {0,0,0,0,1},
        {1,1,0,1,1}
    };
    cout << ob.numDistinctIslands(grid); // Output: 3
    return 0;
}

Phân tích

• Thời gian: O(R*C) – mỗi ô thăm 1 lần.
• Không gian: O(R*C) – đệ quy stack + set lưu chuỗi (tổng độ dài ≤ R*C).

LeetCode 694 "Number of Distinct Islands".