Good Bye 2016 - D

题目链接：http://codeforces.com/contest/750/problem/D

题意：新年烟花爆炸后会往两端45°差分裂。分裂完后变成2部分，之后这2部分继续按这种规则分裂。现在给你每一步分裂的个数。有可能几个部分都是分裂到一个位置，这种情况只算一个。问最后分裂完有多少个。

思路：模拟即可。由于n最多30，每次最多分裂5个。所以总体规模不是很大。但是需要记忆化一下防止TLE。G[][]表示被覆盖的格子。vis[k][i][j][d]表示第k次分裂在位置(i,j)方向为d时是否出现过。然后就BFS模拟。把八个方向以时钟方向表示从0~7。方向k每次分裂相当于分裂了两个方向为(k+1)%8和(k-1+8)%8。

注意可能内存会炸，所以用的bool型数组

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<stdio.h>

#include<queue>

#include<vector>

#include<stack>

#include<map>

#include<set>

#include<time.h>

#include<cmath>

using namespace std;

typedef long long int LL;

const int MAXN =  + ;

int t[MAXN];

bool vis[][MAXN][MAXN][], G[MAXN][MAXN];

int Dir[][] = { , , , , , , -, , -, , -, -, , -, , - };

struct Node{

    int x, y;

    int dir;

    int step;

    Node(int _x = , int _y = , int _dir = , int _step = ) :x(_x), y(_y), dir(_dir), step(_step){};

};

int BFS(int n){

    memset(G, , sizeof(G));

    memset(vis, , sizeof(vis));

    queue<Node>Q;

    Q.push(Node(, , , )); //设起点为250，250

    vis[][][][] = ;

    for (int i = ; i < t[]; i++){ //预处理第1次

        G[ + i*Dir[][]][ + i*Dir[][]] = ;

    }

    while (!Q.empty())

    {

        Node top = Q.front(); Q.pop();

        if (top.step >= n){ break; }

        Node next;

        int k = (top.dir -  + ) % ;

        for (int i = ; i <= t[top.step]; i++){

            G[top.x + i*Dir[k][]][top.y + i*Dir[k][]] = ;

        }

        next.x = top.x + t[top.step] * Dir[k][]; next.y = top.y + t[top.step] * Dir[k][]; next.step = top.step + ; next.dir = k;

        if (!vis[next.step][next.x][next.y][next.dir]){ Q.push(next); vis[next.step][next.x][next.y][next.dir] = ; }

        k = (top.dir + ) % ;

        for (int i = ; i <= t[top.step]; i++){

            G[top.x + i*Dir[k][]][top.y + i*Dir[k][]] = ;

        }

        next.x = top.x + t[top.step] * Dir[k][]; next.y = top.y + t[top.step] * Dir[k][]; next.step = top.step + ; next.dir = k;

        if (!vis[next.step][next.x][next.y][next.dir]){ Q.push(next); vis[next.step][next.x][next.y][next.dir] = ; }

    }

    int ans = ;

    for (int i = ; i < MAXN; i++){

        for (int j = ; j < MAXN; j++){

            ans += G[i][j];

        }

    }

    return ans;

}

int main(){

//#ifdef kirito

//    freopen("in.txt", "r", stdin);

//    freopen("out.txt", "w", stdout);

//#endif

//    int start = clock();

    int n;

    while (scanf("%d", &n) != EOF){

        for (int i = ; i < n; i++){

            scanf("%d", &t[i]);

        }

        printf("%d\n", BFS(n));

    }

//#ifdef LOCAL_TIME

//    cout << "[Finished in " << clock() - start << " ms]" << endl;

//#endif

    return ;

}