作者chadcooper (还在寻找稳健的下一步)
看板Programming
标题[问题] 一个演算法的植树问题
时间Tue May 13 22:15:16 2014
各位程式的高手 大家好
最近跟同学再讨论一个植树的问题
题目如下:
假设给定一个森林的面积
然後每天在森林里选择一小个矩形，在这个矩形里种同一种树(总共可以种很多种树)
试问过了N天後
总共有几种树在这个森林
并问每种树各被种几棵?
这个问题很像是每次选一个矩形涂一种色，
然後做N次之後问每个颜色所占的区块面积，
然後可以对一个区域重复涂色，後面涂的颜色会盖掉前面的颜色。
我同学讨论後现在有想到的只有暴力解
因为要处理的树的种类(颜色)实在太多了
但是我们想说一定有更好的方式可以解这个问题
所以想请问有没有大大能够给我们一些好的想法
让我们可以试试看
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.201.221
※ 文章网址: http://webptt.com/cn.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