HUST 1603 Deadly Disease

题目描述

Queen of honey was deeply shocked when she heard the news that some rooms in her honeycomb is infected with serious virus. To make things worse, each infected room will infect all the rooms which share an edge with it in a second. Because she is so sweet that you think you should help her. however, due to the fact that you do not know much about virus, you decide to be ready to tell her, how many rooms in her honeycomb will be infected in K(0<=K<=10^7) seconds.

输入

First comes an integer T (T<=50), indicating the number of test cases. For each test case, there is two integers N and K. N indicates how many rooms are initially infected, then comes the coordinates of the initially infected rooms, they are represent as (i,j) (0<=i,j<=30). One room can only be infected once and no two coordinates will be the same. Queen's honeycomb should be considered infinitely large.

Coordinates are calculated in this way:

输出

A single integer represent the total number of infected rooms after K seconds.

样例输入

21 2 0 0
2 1 0 0 1 2      

样例输出

19

13      

相当恶心的一道题目，给出初始被感染的点，然后每一秒被感染的点会感染周围的6个点，问第k秒后有多少点被感染了。

首先，对于初始的坐标，都小于30，所以30秒后，所有的初始感染点都会连通，然后考虑这个大连通块的扩展。

对于一个在下一秒会被感染的点，我们将它分成三类，只有一条边与感染点相连，有两条边相连，有三条边相连。

至于更多的边相连的情况，一定会在感染中消失的，所以不用考虑。然后假设这三种点的数量分别为a，b，c

那么下一秒，a和c是不会变的，b=b+a-c,然后感染的块新加了a+b+c块，这些可以通过观察寻找规律。于是问题就解决了。

一开始先模拟感染到全部的点都相连并且没有超过4边的点，之后按照规律就可以直接写出答案了。

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int T, n, x, y, k, cnt, a[4], now;
int f[2][100][100];

void infect()
{
  for (int j = 0; j<100; j++)
  {
    for (int k = 0; k<100; k++)
    {
      if (f[now][j][k])
      {
        f[now ^ 1][j][k]++;
        f[now ^ 1][j + 1][k]++;
        f[now ^ 1][j - 1][k]++;
        f[now ^ 1][j][k + 1]++;
        f[now ^ 1][j][k - 1]++;
        int d = (k & 1) ? -1 : 1;
        f[now ^ 1][j + d][k + 1]++;
        f[now ^ 1][j + d][k - 1]++;
      }
    }
  }
  now ^= 1;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &k);
    memset(f, 0, sizeof(f));
    now = 0;
    for (int i = 0; i<n; i++)
    {
      scanf("%d%d", &x, &y);
      f[now][x + 36][y + 36] = 1;
    }
    for (int i = 1; i <= min(30, k); i++) infect();
    a[1] = a[2] = a[3] = cnt = 0;
    for (int i = 0; i<100; i++)
      for (int j = 0; j<100; j++) if (f[now][i][j]) cnt++;
    if (k <= 30) printf("%d\n", cnt);
    else
    {
      memset(f[now ^ 1], 0, sizeof(f[now ^ 1]));
      infect();
      for (int i = 0; i<100; i++)
        for (int j = 0; j < 100; j++) if (!f[now ^ 1][i][j] && f[now][i][j]) a[f[now][i][j]]++;
      k = k - 30;
      printf("%lld\n", (LL)k*(a[1] + a[2] + a[3]) + (LL)(a[1] - a[3])*k*(k - 1) / 2 + cnt);
    }
  }
  return 0;
}