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

看板Prob_Solve作者 (Wittgenstein)時間12年前 (2012/08/07 22:14), 編輯推噓1(1推 0噓 2→)
留言3則, 2人參與, 最新討論串1/1
考慮一個nxm的方格 我們定義所謂連通集S 不存在非空集合A,B,使得A,B交集為空集合 但A聯集B=S 例如 1. □████□□□□ □██□□□□□□ █████□□□□ □█□□█□□□□ 2. □□███□□□□ □█□□□□□□□ □█□□□□□□□ □█□□□□□□□ 這兩個黑黑的都是連通集(第二個兩個長方形間間有互相碰到 所以也算) 3. □□□□█□□□□ □█□□□□□□□ □█□□□□□□□ □█□□□□□□□ 這個不是連通集 任意給定一個mxn的方格 有什麼好的方法可以計算有多少個連通集? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.107.83
推
08/07 22:20, , 1F
BFS/DFS/用disjoint set計算
08/07 22:20, 1F
→
08/07 22:20, , 2F
你連通集的定義怪怪的...? 存在還是不存在?
08/07 22:20, 2F
對不起打錯了 謝謝指正 ※ 編輯: Wittgenstein 來自: 140.112.107.83 (08/07 22:22) ※ Wittgenstein:轉錄至看板 Math 08/07 22:30
→
08/07 23:49, , 3F
上網搜尋，關鍵字，flood fill
08/07 23:49, 3F
‣ 更多 Wittgenstein 的文章
文章代碼(AID): #1G8IAjA4 (Prob_Solve)