P160 UVa297:(直接看图+解释吧,比较直观了!)
图片发自简书App
题意就是两个大正方形(总共32×32像素)黑色像素合并后输出合并后的正方形里的黑色像素,输入的数据中字母p,e,f分别表示灰,白,黑三色,顺序按树的先序遍历输入。
图片发自简书App
上图解释先序遍历的规律,相信有些没学数据结构的萌新还不理解输入...
下图是结点(理解为上图的球球好像也没太大问题)
每个球球有对应的颜色col,和相连接的4个子球cld[4]。
图片发自简书App
下图为建树函数:buildTree(),合并函数:sumNode()。
合并算法就是遇到黑球直接计算像素,白球直接返回0个像素,遇到灰球就进入子球继续计算黑球。
图片发自简书App
主方法以及运行结果:
图片发自简书App
下图为给的参考答案:
一开始以为是棵树(想歪了),导致了我想了好一阵子。
核心算法是一开始的正方形为32×32的数组(一个点一像素)然后铺黑像素即可,若已经铺过了黑像素则跳过,最后输出黑像素个数,个人感觉像是扫描+打印。
图片发自简书App
图片发自简书App
总结:
我的方法说实话比较直观一点,时间复杂度相对于参考答案更低,但内存消耗会因测试用例的递增而递增(需要建树)。