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;
}