[問題] 計算連通集的數量
看板Prob_Solve (計算數學 Problem Solving)作者Wittgenstein (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
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
08/07 23:49, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
