一本通题解一本通题解——1437：扩散：扩散
题目链接题目链接
一本通OJ：http://ybt.ssoier.cn:8088/problem_show.php?pid=1437。
我的OJ：http://47.110.135.197/problem.php?id=4462。
题目题目
题目描述题目描述
一个点每过一个单位时间就会向四个方向扩散一个距离，如图。
上图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。
题目分析题目分析
根据题意，个点每过一个单位时间就会向四个方向扩散一个距离。我们使用输入样例来分析输出结果。开始我们有两个点
（0, 0）和（5, 5）。时间和扩散点坐标如下表。
时间 A 点 B 点
t=0 （0, 0） （5, 5）
上 左 下 右 上 左 下 右
t=1 （0, 1） （1, 0）
（0, -
1）
（-1, 0） （5, 6） （6, 5） （5, 4） （4, 5）
t=2 （0, 2） （2, 0）
（0, -
2）
（-2, 0） （5, 7） （7, 5） （5, 3） （3, 5）
t=3 （0, 3） （3, 0）
（0, -
3）
（-3, 0） （5, 8） （8, 5） （5, 2） （2, 5）
t=4 （0, 4） （4, 0）
（0, -
4）
（-4, 0） （5, 9） （9, 5） （5, 1） （1, 5）
t=5 （0, 5） （5, 0）
（0, -
5）
（-5, 0） （5, 10） （10, 5） （5, 0） （0, 5）
……
下面我们绘制一下当 t=5 的时候情况，如下图所示，黑色为 （0, 0）点扩散情况，红色为（5, 5）点扩散情况。可以非常清楚
的看到当 t=5 的时候，发生了连通性。
资源评论
