一个简简单单的算法专题，黑点扩散

旭哥520

小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点:(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色,其它位置都是白色的。
每过一分钟,黑色就会扩散一点。具体的,如果一个格子里面是黑色,它就会扩散到上、下、左、右四个相邻的格子中,使得这四个格子也变成黑色(如果原来就是黑色,则还是黑色)。
请问,经过 2020 分钟后,画布上有多少个格子是黑色的。


-----------------------------------

分析：纯数数题。首先可以模拟一下这个无限大的点，在任一一方格内，1分钟扩散的黑点数，不难得出。为5。

所以，我们只要取出最小的扩散点数，和最大的扩散点数，然后暴力枚举即可。





答案是：20312088

海洋之心365

晴天大佬

旭哥520

一路生花 发表于 2022-3-6 00:13
没看懂

算法题就是这样，哈哈。我这属于最简单的，还有什么bfs之类的，也在学习中。

把算法搞通了一点，写程序时遇到逻辑性问题，也许就能够想出一些办法，只有益处，没有坏处。

可以想象，1分钟扩展1个点，可以想象成扩展1次，试想，在一个无限大的方格内，我在一点上点一个黑点，然后扩展一次，就会向上下左右各扩展一个点。就比如如下这个图片

--------------
・ ・ ・ ・
・ ・ 〇 ・
・ ・ ・ ・
・ ・ ・ ・
--------------

扩展一次，肯定会变成这样

-------------
・ ・ 〇 ・
・ 〇 〇 〇
・ ・ 〇 ・
・ ・ ・ ・
-------------

可以看到，扩展一次是以扩散点向上下左右扩散的，所以我们取得扩散点的坐标，然后看扩展几次即可。
比如说上面这个图，扩展了一次，其扩展点是（3，2），那么，扩展一次，最大点就是3+1=4，最小点是3-1=2，我们只需要将X坐标从2枚举到4即可，同样地，Y坐标，2-1=1，2+1=3，所以Y坐标就是从1枚举到3，然后嵌套循环，拿所枚举到点与原点（3，2）相减取绝对值，再判断与原点相减，是否小于扩展点的数，是则累计加1，否则加0（舍弃），即可判断是不是扩展的点的。

例如：

for ( i=2;i<=4;i++)
{
   for(j=1;j<=3;j++）
    {

           依次循环，(2,1),(2,2),(2,3);(3,1),(3,2),(3,3);(4,1),4,2),(4,3)。再把2-原坐标X点（3）+1-原坐标Y点（2）<2，不符合则不加1，如果符合就加1，最后肯定只有上面几个“〇“符合。最终结果也就是5。

    }
}

Suky

没看懂