PTT數位生活區 / Fortran

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

看板Fortran作者 (Touerin)時間8年前 (2016/07/22 10:30), 8年前編輯推噓2(2推 0噓 12→)
留言14則, 4人參與, 最新討論串1/1
假設有一個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
→
07/23 08:45, , 1F
flood fill
07/23 08:45, 1F
這個我會找找看的!
→
07/24 01:13, , 2F
首先你要定義 假設一個2x2矩陣 11和22是1 12和21是0
07/24 01:13, 2F
→
07/24 01:14, , 3F
這樣算不算1是連起來的？ 還是一個1他對角的也要是0才算
07/24 01:14, 3F
→
07/24 01:14, , 4F
分開
07/24 01:14, 4F
→
07/24 01:15, , 5F
你有了明確得"區塊"的定義 就可以用掃描的方式找出來了
07/24 01:15, 5F
只有對角線相鄰的話就不算喔 掃描是指?
→
07/25 13:56, , 6F
就是一格一格去算 這招叫暴力法
07/25 13:56, 6F
一格一格算如何分群? ※ 編輯: ej03xu3 (140.115.36.159), 07/25/2016 16:49:35
推
07/25 17:57, , 7F
用Breadth-First-Search
07/25 17:57, 7F
→
07/25 17:58, , 8F
矩陣元素定為Vertex定義「相鄰」的元素之間，有Edge連接
07/25 17:58, 8F
→
07/25 17:59, , 9F
然後就可以套入BFS了 效率為O(|V|+|E|)
07/25 17:59, 9F
→
07/25 17:59, , 10F
在這個例子裡面|V|為行數x列數 mxn
07/25 17:59, 10F
→
07/25 18:00, , 11F
|E|約和|V|差不多(雖然約為4倍，但同樣complexity)
07/25 18:00, 11F
→
07/25 18:01, , 12F
BFS在你矩陣很大時 效率比暴力法好
07/25 18:01, 12F
→
07/25 18:01, , 13F
不過如果你矩陣不大 較沒差
07/25 18:01, 13F
推
07/26 13:25, , 14F
推樓上方法 找本資料結構教科書來看 BFS一定有教
07/26 13:25, 14F
‣ 更多 ej03xu3 的文章
文章代碼(AID): #1NaOLU9h (Fortran)
Fortran 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ej03xu3 的文章
文章代碼(AID): #1NaOLU9h (Fortran)