作者Wittgenstein (Wittgenstein)
看板Prob_Solve
标题[问题] 计算连通集的数量
时间Tue Aug 7 22:14:02 2012
考虑一个nxm的方格
我们定义所谓连通集S
不存在非空集合A,B,使得A,B交集为空集合 但A联集B=S
例如
1.
□████□□□□
□██□□□□□□
█████□□□□
□█□□█□□□□
2.
□□███□□□□
□█□□□□□□□
□█□□□□□□□
□█□□□□□□□
这两个黑黑的都是连通集(第二个两个长方形间间有互相碰到 所以也算)
3.
□□□□█□□□□
□█□□□□□□□
□█□□□□□□□
□█□□□□□□□
这个不是连通集
任意给定一个mxn的方格
有什麽好的方法可以计算有多少个连通集?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.107.83
1F：推 suhorng:BFS/DFS/用disjoint set计算 08/07 22:20
2F：→ suhorng:你连通集的定义怪怪的...? 存在还是不存在? 08/07 22:20
对不起打错了 谢谢指正
※ 编辑: Wittgenstein 来自: 140.112.107.83 (08/07 22:22)
※ Wittgenstein:转录至看板 Math 08/07 22:30
3F：→ wtvwtvwtv200:上网搜寻，关键字，flood fill 08/07 23:49