博客

问题描述

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点：( 0 , 0)，( 2020 , 11 )，( 11 , 14 )，( 2000， 2000 )。只有这几个格子上有黑色，其它位置都是白色的。

每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。

请问，经过 2020 分钟后，画布上有多少个格子是黑色的。

解题思路

通过模拟的思想，可以画出几个，找出其中的规律



经过2020分钟后，一个点的上下左右最多加2020。由于题目中说的是无限大的画布，考虑到数组下标不能为负数，所以我们可以将0,0这个点平移(3000,3000)，相应的，其他点也加（3000,3000）这样做的好处是，经过2020次，下标一定大于0。这里开辟了一个[10000][10000]的数组，也可以不用这么大，最多遍历整个数组，如果值为1的话，则说明变成黑色了，cnt++即可。

代码

public class Main{

    static int[][] graph = new int[10000][10000];
    static void func(int x,int y)
    {
        int t = 0;
        // 左半部分
        for(int i= x-2020;i<=x-1;i++)
        {
            for(int j=y-t;j<=y+t;j++)
            {
                //System.out.println(i+" "+j);
                graph[i][j] = 1;
            }
            t++;
        }
        // 中间部分
        for(int i=y-2020;i<=y+2020;i++)
            graph[x][i] = 1;

        t = 0;
        // 右半部分
        for(int i= x+2020;i>=x+1;i--)
        {
            for(int j=y-t;j<=y+t;j++)
            {
                graph[i][j] = 1;
            }
            t++;
        }
    }

    public static void main(String[] args) {

       graph[0+3000][0+3000] = 1;
       graph[2020+3000][11+3000] = 1;
       graph[11+3000][14+3000] = 1;
       graph[2000+3000][2000+3000] = 1;
       func(3000,3000);
       func(2020+3000,11+3000);
       func(11+3000,14+3000);
       func(2000+3000,2000+3000);
       int cnt = 0;
       for(int i=0;i<10000;i++)
       {
           for(int j=0;j<10000;j++)
           {
               if(graph[i][j]==1)
                   cnt++;
           }
       }
       System.out.println(cnt);
    }
}

答案

20312088