home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Number of Distinct Islands II (จำนวนเกาะที่แตกต่างกัน ระดับ 2) ใน C++

สมมติว่าเรามีอาเรย์ 2 มิติ binary ไม่ว่างเปล่า ชื่อ grid ที่นี่ เกาะ (island) คือกลุ่มของ 1 (แทนที่ดิน) ที่เชื่อมต่อกัน 4 ทิศทาง เราสามารถสมมติได้ว่า ขอบทั้ง 4 ด้านของ grid ถูกล้อมรอบด้วยน้ำ

เราต้องนับจำนวนเกาะที่แตกต่างกัน (distinct islands) เกาะหนึ่งถูกพิจารณาว่าเหมือนอีกเกาะหนึ่ง หากพวกมันมีรูปร่างเดียวกัน หรือมีรูปร่างเดียวกันหลังจากการหมุน 90, 180, หรือ 270 องศาเท่านั้น หรือการสะท้อน (reflection) ทิศซ้าย/ขวา หรือ บน/ล่าง

ดังนั้น หากอินพุทคือ:

11000
10000
00001
00011

ผลลัพธ์จะเป็น 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

  • กำหนด map m

  • กำหนดฟังก์ชัน dfs() รับ i, j, grid, idx

    • ถ้า i,j อยู่นอกขอบเขต grid หรือ grid[i][j] == 0: return

    • grid[i][j] := 0

    • ใส่ {i, j} ลง m[idx]

    • dfs(i+1, j, grid, idx), dfs(i-1, j, grid, idx), dfs(i, j-1, grid, idx), dfs(i, j+1, grid, idx)

  • กำหนดฟังก์ชัน norm() รับอาเรย์ v

    • กำหนดอาเรย์ 2 มิติ s ของ pair ขนาด 8 แถว

    • for i := 0 ถึง v.size()-1:

      • x := v[i].first, y := v[i].second

      • ใส่ {x, y} ลง s[0], {x, -y} ลง s[1], {-x, y} ลง s[2], {-x, -y} ลง s[3]

      • ใส่ {y, x} ลง s[4], {y, -x} ลง s[5], {-y, x} ลง s[6], {-y, -x} ลง s[7]

    • for i := 0 ถึง 7: จัดเรียง s[i]

    • for i := 0 ถึง 7, for j := 1 ถึง v.size()-1:

      • s[i][j].first := s[i][j].first - s[i][0].first

      • s[i][j].second := s[i][j].second - s[i][0].second

    • s[i][0] := {0, 0}

    • จัดเรียง s

    • คืนค่า s[0]

  • จาก main method:

    • กำหนด set pts

    • cnt := 1

    • for i := 0 ถึง grid.size()-1, for j := 0 ถึง grid[0].size()-1:

      • ถ้า grid[i][j] == 1: cnt++; dfs(i, j, grid, cnt); ใส่ norm(m[cnt]) ลง pts

    • คืนค่า ขนาดของ pts

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

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

class Solution {
public:
    map>> m;

    void dfs(int i, int j, vector>& grid, int idx) {
        if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j])
            return;
        grid[i][j] = 0;
        m[idx].push_back({i, j});
        dfs(i + 1, j, grid, idx);
        dfs(i - 1, j, grid, idx);
        dfs(i, j - 1, grid, idx);
        dfs(i, j + 1, grid, idx);
    }

    vector> norm(vector> v) {
        vector>> s(8);
        for (int i = 0; i < v.size(); i++) {
            int x = v[i].first;
            int y = v[i].second;
            s[0].push_back({x, y});
            s[1].push_back({x, -y});
            s[2].push_back({-x, y});
            s[3].push_back({-x, -y});
            s[4].push_back({y, x});
            s[5].push_back({y, -x});
            s[6].push_back({-y, x});
            s[7].push_back({-y, -x});
        }
        for (int i = 0; i < s.size(); i++) {
            sort(s[i].begin(), s[i].end());
        }
        for (int i = 0; i < s.size(); i++) {
            for (int j = 1; j < v.size(); j++) {
                s[i][j].first = s[i][j].first - s[i][0].first;
                s[i][j].second = s[i][j].second - s[i][0].second;
            }
            s[i][0].first = 0;
            s[i][0].second = 0;
        }
        sort(s.begin(), s.end());
        return s[0];
    }

    int numDistinctIslands2(vector>& grid) {
        set>> pts;
        int cnt = 1;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    cnt++;
                    dfs(i, j, grid, cnt);
                    pts.insert(norm(m[cnt]));
                }
            }
        }
        return pts.size();
    }
};

int main() {
    Solution ob;
    vector> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}};
    cout << (ob.numDistinctIslands2(v));
    return 0;
}

อินพุต

{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}

เอาต์พุต

1