作者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/m.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