作者chadcooper (還在尋找穩健的下一步)
看板Programming
標題[問題] 一個演算法的植樹問題
時間Tue May 13 22:15:16 2014
各位程式的高手 大家好
最近跟同學再討論一個植樹的問題
題目如下:
假設給定一個森林的面積
然後每天在森林裡選擇一小個矩形，在這個矩形裡種同一種樹(總共可以種很多種樹)
試問過了N天後
總共有幾種樹在這個森林
並問每種樹各被種幾棵?
這個問題很像是每次選一個矩形塗一種色，
然後做N次之後問每個顏色所占的區塊面積，
然後可以對一個區域重複塗色，後面塗的顏色會蓋掉前面的顏色。
我同學討論後現在有想到的只有暴力解
因為要處理的樹的種類(顏色)實在太多了
但是我們想說一定有更好的方式可以解這個問題
所以想請問有沒有大大能夠給我們一些好的想法
讓我們可以試試看
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.201.221
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Programming/M.1399990519.A.B74.html
1F：推 fongan:推這個問題有深度140.113.136.218 05/13 22:49
2F：推 rebaudiana:每塗一個矩形，就把較該矩形晚塗的矩 42.78.69.77 05/14 00:08
3F：→ rebaudiana:形檢查過一遍。每次被蓋到最多只要分 42.78.69.77 05/14 00:09
4F：→ rebaudiana:成沒背蓋到的四小塊遞歸處理就好了。這 42.78.69.77 05/14 00:09
5F：→ rebaudiana:樣應該是O(N^2)？ 42.78.69.77 05/14 00:09
6F：推 fenzhang:線段樹+掃描線 114.44.248.5 05/14 00:58
7F：推 AIGecko:假如矩形的長度單位為整數 每個點有座標140.122.218.114 05/14 01:17
8F：→ AIGecko:然後用Hash紀錄每點的樹種 可以被覆蓋140.122.218.114 05/14 01:18
9F：→ AIGecko:可能另外用一個陣列紀錄哪些點有種過樹140.122.218.114 05/14 01:19
10F：→ AIGecko:還有個Hash紀錄哪些數有種過140.122.218.114 05/14 01:20
11F：→ AIGecko:僅限於邊長為整數的情況...140.122.218.114 05/14 01:21