洛谷:P5461:赦免战俘


洛谷:P5461:赦免战俘

Table of Contents

题目

P5461:赦免战俘

分析

这道题不难。根据题意,直觉告诉我们,可以分而治之:每个区域(除了左上角区域),都可以再分四个区域;这四个新的小区域,除了左上角的其他三个区域,还可以继续分割……由于这个区间的长宽都是\(2^n\),可以保证不断均匀分割——直到边长为1为止——看!分割的终止条件也出来了!。

接下来就是分析一个正方形的设定。一般而言,在编程中,正方形由三个参数确定。本题中可以用左上角的坐标(x, y)以及边长size来决定。知道原始正方形的坐标后,新的四个区域正方形的坐标可以确定如下:

注意,这里的xy坐标轴和方向和我们常用的不同。X轴是从上到下(和数组的行数对应),Y轴是从左到右(和数组的列数对应)。

基本的处理流程就是:

flowchart TD A["当前正方形的坐标(x, y)和边长size"]--> Q{当前size为1?} -->|否| B[计算除左上角的另外三个区域坐标和边长] -->|递归| A Q-->|是|C[当前位置标为1,返回。]

根据这个核心处理流程,我们一开始就应该将所有位置设置为0(全都赦免)。

答案

Solution

思考

这是一道很好的理解递归和分治的入门题目。

上一篇 下一篇