Number of Distinct Islands – นับเกาะที่แตกต่างกันใน C++

ปัญหา: Number of Distinct Islands

กำหนด Grid 2D (0 = น้ำ, 1 = บก) เกาะ = กลุ่ม 1 ติดกัน 4 ทิศทาง หาจำนวน เกาะที่แตกต่างกัน (distinct)
เกาะเหมือนกัน = สามารถ เลื่อน (translate) ทับกันได้ (ไม่นับการหมุน/พลิก)

ตัวอย่าง

Grid:

1 1 0 1 1
1 0 0 0 0
0 0 0 0 1
1 1 0 1 1

Output: 3 (มีรูปทรงเกาะ 3 แบบ)

แนวทางแก้ปัญหา: DFS + Shape Encoding

ข้อสังเกตสำคัญ

เพื่อเปรียบเทียบรูปทรงเกาะโดยไม่สนตำแหน่ง → ใช้ Relative Path Signature
บันทึกเส้นทาง DFS: 's' (start), 'u','d','l','r' (ทิศทาง), 'b' (backtrack)

ขั้นตอน

1. วนทุกเซลล์ ถ้าเป็น 1 → เริ่ม DFS
2. DFS: mark visited (set 0), บันทึกทิศทางเดิน, backtrack บันทึก 'b'
3. ได้ string signature → ใส่ set
4. ขนาด set = จำนวนเกาะที่แตกต่าง

ตัวอย่างโค้ด C++

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

class Solution {
public:
    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])
            return;
        grid[x][y] = 0;
        path += dir;
        dfs(x+1, y, grid, path, 'r'); // down (row+1)
        dfs(x-1, y, grid, path, 'l'); // up
        dfs(x, y+1, grid, path, 'd'); // right
        dfs(x, y-1, grid, path, 'u'); // left
        path += 'b'; // backtrack
    }

    int numDistinctIslands(vector<vector<int>>& grid) {
        unordered_set<string> shapes;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j]) {
                    string path = "";
                    dfs(i, j, grid, path, 's');
                    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); // 3
    return 0;
}

วิธีอื่น: Normalize Coordinates

เก็บพิกัด relative to จุดเริ่มต้น (min row, min col) → sort → ทำเป็น string

vector<pair<int,int>> cells;
dfs_collect(x, y, cells, x, y); // pass base_x, base_y
// normalize: (x-base_x, y-base_y)
// sort cells, convert to string

ความซับซ้อน

• เวลา: O(R × C) – แต่ละเซลล์เยี่ยม 1 ครั้ง
• พื้นที่: O(R × C) – recursion stack + path strings

ข้อสังเกต

• LeetCode 694
• Path signature ด้วย backtracking ('b') สำคัญ – แยกได้ระหว่างรูปทรงที่ต่างกันแต่มีทิศทางเดินคล้าย
• เช่น: ⬛⬜ vs ⬜⬛ – path signature จะต่างกัน
• การหมุน/พลิก ไม่ถือว่าเหมือนกัน (โจทย์ระบุ translate only)