[問題] 計算連通集的數量

[Wittgenstein (Wittgenstein)]

考慮一個nxm的方格
我們定義所謂連通集S
不存在非空集合A,B,使得A,B交集為空集合 但A聯集B=S

例如
1.
□████□□□□
□██□□□□□□
█████□□□□
□█□□█□□□□
2.
□□███□□□□
□█□□□□□□□
□█□□□□□□□
□█□□□□□□□
這兩個黑黑的都是連通集(第二個兩個長方形間間有互相碰到 所以也算)

3.
□□□□█□□□□
□█□□□□□□□
□█□□□□□□□
□█□□□□□□□
這個不是連通集


任意給定一個mxn的方格
有什麼好的方法可以計算有多少個連通集?
謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.107.83
推 suhorng:BFS/DFS/用disjoint set計算
→ suhorng:你連通集的定義怪怪的...? 存在還是不存在?
對不起打錯了 謝謝指正
※ 編輯: Wittgenstein    來自: 140.112.107.83       (08/07 22:22)
※ Wittgenstein:轉錄至看板 Math                                    08/07 22:30
→ wtvwtvwtv200:上網搜尋，關鍵字，flood fill