作者ej03xu3 (Touerin)
看板Fortran
标题[问题] 辨别二维区块的方式?
时间Fri Jul 22 10:30:50 2016
假设有一个10*10的二维矩阵
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0
其中有两块有含数字1的封闭区块
在你不知道这两块的位置和大小的情况下
你只知道二维矩阵的值有1有0
要怎麽分辨这两个区块呢?
例如写成A和B区块 变成:
0 0 0 0 0 0 0 0 0 0
0 0
A A A A A 0 0 0
0
A A A A A A A 0 0
0
A A A A A A 0 0 0
0 0
A A A A A 0 0 0
0 0 0
A A 0 0 0 0 0
0 0 0 0 0 0 0
B 0 0
0 0 0 0 0 0
B B B 0
0 0 0 0 0
B B B B 0
0 0 0 0 0 0 0 0 0 0
--
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Fortran/M.1469154654.A.26B.html
※ 编辑: ej03xu3 (140.115.36.159), 07/22/2016 10:32:10
1F：→ blc: flood fill 07/23 08:45
这个我会找找看的!
2F：→ noonee: 首先你要定义 假设一个2x2矩阵 11和22是1 12和21是0 07/24 01:13
3F：→ noonee: 这样算不算1是连起来的？ 还是一个1他对角的也要是0才算 07/24 01:14
4F：→ noonee: 分开 07/24 01:14
5F：→ noonee: 你有了明确得"区块"的定义 就可以用扫描的方式找出来了 07/24 01:15
只有对角线相邻的话就不算喔 扫描是指?
6F：→ noonee: 就是一格一格去算 这招叫暴力法 07/25 13:56
一格一格算如何分群?
※ 编辑: ej03xu3 (140.115.36.159), 07/25/2016 16:49:35
7F：推 alen332l: 用Breadth-First-Search 07/25 17:57
8F：→ alen332l: 矩阵元素定为Vertex定义「相邻」的元素之间，有Edge连接 07/25 17:58
9F：→ alen332l: 然後就可以套入BFS了 效率为O(|V|+|E|) 07/25 17:59
10F：→ alen332l: 在这个例子里面|V|为行数x列数 mxn 07/25 17:59
11F：→ alen332l: |E|约和|V|差不多(虽然约为4倍，但同样complexity) 07/25 18:00
12F：→ alen332l: BFS在你矩阵很大时 效率比暴力法好 07/25 18:01
13F：→ alen332l: 不过如果你矩阵不大 较没差 07/25 18:01
14F：推 Sunal: 推楼上方法 找本资料结构教科书来看 BFS一定有教 07/26 13:25