题目
分析
这道题不难。根据题意,直觉告诉我们,可以分而治之:每个区域(除了左上角区域),都可以再分四个区域;这四个新的小区域,除了左上角的其他三个区域,还可以继续分割……由于这个区间的长宽都是\(2^n\),可以保证不断均匀分割——直到边长为1为止——看!分割的终止条件也出来了!。
接下来就是分析一个正方形的设定。一般而言,在编程中,正方形由三个参数确定。本题中可以用左上角的坐标(x, y)
以及边长size
来决定。知道原始正方形的坐标后,新的四个区域正方形的坐标可以确定如下:
注意,这里的x
和y
坐标轴和方向和我们常用的不同。X轴是从上到下(和数组的行数对应),Y轴是从左到右(和数组的列数对应)。
基本的处理流程就是:
根据这个核心处理流程,我们一开始就应该将所有位置设置为0
(全都赦免)。
答案
思考
这是一道很好的理解递归和分治的入门题目。