[問題] 辨別二維區塊的方式?

[ej03xu3 (Touerin)]

假設有一個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://www.ptt.cc/bbs/Fortran/M.1469154654.A.26B.html
※ 編輯: ej03xu3 (140.115.36.159), 07/22/2016 10:32:10
→ blc: flood fill
這個我會找找看的!
→ noonee: 首先你要定義 假設一個2x2矩陣  11和22是1 12和21是0
→ noonee: 這樣算不算1是連起來的？ 還是一個1他對角的也要是0才算
→ noonee: 分開
→ noonee: 你有了明確得"區塊"的定義 就可以用掃描的方式找出來了
只有對角線相鄰的話就不算喔 掃描是指?
→ noonee: 就是一格一格去算 這招叫暴力法
一格一格算如何分群?
※ 編輯: ej03xu3 (140.115.36.159), 07/25/2016 16:49:35
推 alen332l: 用Breadth-First-Search
→ alen332l: 矩陣元素定為Vertex定義「相鄰」的元素之間，有Edge連接
→ alen332l: 然後就可以套入BFS了  效率為O(|V|+|E|)
→ alen332l: 在這個例子裡面|V|為行數x列數 mxn
→ alen332l: |E|約和|V|差不多(雖然約為4倍，但同樣complexity)
→ alen332l: BFS在你矩陣很大時 效率比暴力法好
→ alen332l: 不過如果你矩陣不大 較沒差
推 Sunal: 推樓上方法 找本資料結構教科書來看 BFS一定有教