[問題] 一個演算法的植樹問題

[chadcooper (還在尋找穩健的下一步)]

各位程式的高手 大家好

最近跟同學再討論一個植樹的問題

題目如下:

假設給定一個森林的面積

然後每天在森林裡選擇一小個矩形，在這個矩形裡種同一種樹(總共可以種很多種樹)

試問過了N天後

總共有幾種樹在這個森林

並問每種樹各被種幾棵?


這個問題很像是每次選一個矩形塗一種色，

然後做N次之後問每個顏色所占的區塊面積，

然後可以對一個區域重複塗色，後面塗的顏色會蓋掉前面的顏色。




我同學討論後現在有想到的只有暴力解

因為要處理的樹的種類(顏色)實在太多了

但是我們想說一定有更好的方式可以解這個問題

所以想請問有沒有大大能夠給我們一些好的想法

讓我們可以試試看



感謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.201.221
※ 文章網址: http://www.ptt.cc/bbs/Programming/M.1399990519.A.B74.html
推 fongan:推這個問題有深度
推 rebaudiana:每塗一個矩形，就把較該矩形晚塗的矩
→ rebaudiana:形檢查過一遍。每次被蓋到最多只要分
→ rebaudiana:成沒背蓋到的四小塊遞歸處理就好了。這
→ rebaudiana:樣應該是O(N^2)？
推 fenzhang:線段樹+掃描線
推 AIGecko:假如矩形的長度單位為整數 每個點有座標
→ AIGecko:然後用Hash紀錄每點的樹種 可以被覆蓋
→ AIGecko:可能另外用一個陣列紀錄哪些點有種過樹
→ AIGecko:還有個Hash紀錄哪些數有種過
→ AIGecko:僅限於邊長為整數的情況...