จำนวนหมู่เกาะที่แตกต่าง II ใน C++

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

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

ดังนั้นหากอินพุตเป็นแบบนั้น

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

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

• กำหนดหนึ่งแผนที่ m

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ i, j, grid, idx

• หาก i และ j อยู่ในช่วงของกริดและกริด[i,j] เป็น 0 ดังนั้น −

  • กลับ

• กริด[i, j] :=0

• ใส่ { i, j } ที่ส่วนท้ายของ m[idx]

• dfs(i + 1, j, กริด, idx)

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

• dfs(i, j - 1, กริด, idx)

• dfs(i, j + 1, กริด, idx)

• กำหนดหนึ่งฟังก์ชัน norm() ซึ่งจะใช้อาร์เรย์ v

  • กำหนดคู่อาร์เรย์ 2 มิติหนึ่งคู่ที่มี 8 แถว

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • x :=v[i].first

    • y :=v[i].วินาที

    • ใส่ { 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]

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • เรียงลำดับอาร์เรย์ s[i]

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • สำหรับการเริ่มต้น j :=1 เมื่อ j <ขนาด v อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ −

      • s[i, j].first :=s[i, j].first - s[i, 0].ก่อน

      • s[i, j].second :=s[i, j].second - s[i, 0].วินาที

    • s[i, 0].first :=0

    • s[i, 0].วินาที :=0

  • เรียงลำดับอาร์เรย์ s

  • กลับ s[0]

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดแต้มหนึ่งชุด

• cnt :=1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของกริด อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า grid[i, j] เหมือนกับ 1 แล้ว −

      • (เพิ่มขึ้นอีก 1)

      • dfs(i, j, กริด, cnt)

      • แทรก norm(m[cnt]) ลงใน pts

• ขนาดผลตอบแทนของ pts

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;คลาสโซลูชัน { สาธารณะ:แผนที่ >> m; โมฆะ dfs(int i, int j, vector >&grid, int idx){ if (i>=grid.size() || j>=grid[0].size() || i <0 || !grid[i][j]) กลับ; ตาราง[i][j] =0; m[idx].push_back({ i, j }); dfs(i + 1, j, กริด, idx); dfs(i - 1, j, กริด, idx); dfs(i, j - 1, กริด, idx); dfs(i, j + 1, กริด, idx); } เวกเตอร์ <คู่ > บรรทัดฐาน (เวกเตอร์ <คู่ > v){ vector>> s(8); สำหรับ (int i =0; i >&ตาราง) { set>> pts; int cnt =1; สำหรับ (int i =0; i > v ={{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0 ,0,1,1}}; ศาล <<(ob.numDistinctIslands2(v));}

อินพุต

ผลลัพธ์

1