Codefroces 750D：New Year and Fireworks（BFS）

时间：2021-12-13 08:48:14

http://codeforces.com/contest/750/problem/D

题意：烟花会绽放n次，每次会向前推进t[i]格，每次绽放会向左右45°绽放，问有烟花的格子数。

思路：n = 30， t = 5，所以最多推进150格。范围很小，开一个300*300的数组，初始位置在（150， 150），直接BFS。

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define N 310

 typedef long long LL;

 struct P {

     int x, y, step, dir;

     P () {}

     P (int x, int y, int step, int dir) : x(x), y(y), step(step), dir(dir) {}

 };

 int ans, t[N];

 bool mp[N][N];

 bool vis[N][N][][];

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

 // 八个方向顺时针

 void BFS(int n) {

     queue<P> que;

     while(!que.empty()) que.pop();

     memset(vis, , sizeof(vis));

     memset(mp, , sizeof(mp));

     ans = ;

     vis[][][][] = ; // 初始位置

     que.push(P(, , , ));

     while(!que.empty()) {

         P f = que.front(); que.pop();

         int nx = f.x, ny = f.y, step = f.step, dd = f.dir;

         for(int i = ; i <= t[step]; i++) { // 处理这一层的绽放情况

             nx += d[dd][];

             ny += d[dd][];

             mp[nx][ny] = ;

         }

         if(step < n) { // 向左右绽放

             int dl = ((dd - ) + ) % , dr = (dd + ) % ;

             if(!vis[nx][ny][step+][dl]) {

                 vis[nx][ny][step+][dl] = ;

                 que.push(P(nx, ny, step + , dl));

             }

             if(!vis[nx][ny][step+][dr]) {

                 vis[nx][ny][step+][dr] = ;

                 que.push(P(nx, ny, step + , dr));

             }

         }

     }

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

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

             if(mp[i][j]) ans++;

 }

 int main() {

     int n;

     cin >> n;

     for(int i = ; i <= n; i++) cin >> t[i];

     BFS(n);

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

     return ;

 }

相关文章