CFR 750 D. New Year and Fireworks ( DP )

題意：
放煙火，煙火有 N 個階段，在第 i 個階段會往前噴 T[ i ] 個單位長度後，向 +45度和 -45度分岔繼續噴，並同時變成下個階段。求噴完會經過多少格子。

資料規模：
1 ≤ N ≤ 30
1 ≤ T[ i ] ≤ 5
時間限制：2500 ms
空間限制：256 MB

解法：
最遠只會噴到 N * T[ i ] = 150 遠，因此真正會造訪的格子不會超過 300 ^ 2 個。用一個 set 紀錄這個點有沒有當作特定階段特定方向的噴發起點避免重複計算即可。

時間 / 空間複雜度：
O( 30 * 8 * 300 ^ 2 lg ( 30 * 8 * 300 ^ 2 ) ) / O( 30 * 8 * 300 ^ 2 )

int N;
vi T;

void init(){
  cin >> N;
  T = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> T[ i ];
  }
}

const int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
const int dy[] = { 1, 1, 0, -1, -1, -1, 0, 1 };

set< tuple< int, int, int, int > > vis;
set< pii > coordinate;

void preprocess(){
  queue< tuple< int, int, int, int > > que;
  que.emplace( 0, 0, 0, 0 );
  vis.emplace( 0, 0, 0, 0 );
  coordinate.emplace( 0, 0 );
  while( not que.empty() ){
    int step, x, y, dir; tie( step, x, y, dir ) = que.front(); que.pop();
    int nx = x, ny = y;
    for( int i = 0; i < T[ step ] - 1; ++i ){
      nx += dx[ dir ];
      ny += dy[ dir ];
      coordinate.emplace( nx, ny );
    }
    if( step + 1 < N and not vis.count( make_tuple( step + 1, nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ], ( dir + 1 ) % 8 ) ) ){
      vis.emplace( step + 1, nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ], ( dir + 1 ) % 8 );
      coordinate.emplace( nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ] );
      que.emplace( step + 1, nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ], ( dir + 1 ) % 8 );
    }
    if( step + 1 < N and not vis.count( make_tuple( step + 1, nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ], ( dir - 1 + 8 ) % 8 ) ) ){
      vis.emplace( step + 1, nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ], ( dir - 1 + 8 ) % 8 );
      coordinate.emplace( nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ] );
      que.emplace( step + 1, nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ], ( dir - 1 + 8 ) % 8 );
    }
  }
}

void solve(){
  cout << coordinate.size() << endl;
}