CodeForces

因为烟花的最大范围是各个方向150格

所以最大的空间应该是 300*300

BFS和DFS均可

模拟每一个烟花爆炸的过程但是要注意需要一个数组来排重

在某一个爆炸点如果爆炸的方向和爆炸的层数是相同的那么就不再讨论这个爆炸点

因此这个排重数组需要记录的信息： x, y, dir, step

以下是BFS代码

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 
 9 int n, t[32], cnt = 0;
10 int sky[312][312];
11 bool mark[312][312][32][8];
12 int d[][2] = { {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} };
13 
14 
15 struct Node
16 {
17     int x, y;
18     int dir, step;
19 };
20 void bfs(int x, int y)
21 {
22     Node start;
23     start.x = x;
24     start.y = y;
25     start.dir = 0;
26     start.step = 0;
27     queue<Node> que;
28     int nx, ny;
29     que.push(start);
30     mark[x][y][start.step][start.dir] = 1;//一定要 否则内存超 数组去重
31     while (!que.empty())
32     {
33         Node crt = que.front();
34         que.pop();
35         nx = crt.x;
36         ny = crt.y;
37         for (int i = 0; i < t[crt.step]; i++)
38         {
39             nx += d[crt.dir][0];
40             ny += d[crt.dir][1];
41            // mark[nx][ny][crt.dir][crt.step] = 1;
42             if (!sky[nx][ny])
43             {
44                 cnt++;
45                 sky[nx][ny] = 1;
46             }
47         }
48         if (crt.step == n-1) continue;
49         Node next;
50         next.x = nx;
51         next.y = ny;
52         next.step = crt.step+1;
53         next.dir = (crt.dir+1)%8;
54         if (!mark[nx][ny][next.dir][next.step])
55         {
56             mark[nx][ny][next.dir][next.step] = 1;//注意去重数组的位置
57             que.push(next);
58         }
59         next.dir = (crt.dir+7)%8;
60         if (!mark[nx][ny][next.dir][next.step])
61         {
62             mark[nx][ny][next.dir][next.step] = 1;
63             que.push(next);
64         }
65     }
66     return ;
67 }
68 
69 int main()
70 {
71     freopen("in.txt", "r", stdin);
72     scanf("%d", &n);
73     for (int i = 0; i < n; i++)
74     {
75         scanf("%d", &t[i]);
76     }
77     memset(sky, 0, sizeof(sky));
78     memset(mark, 0, sizeof(mark));
79     cnt = 0;
80     bfs(156, 156);
81     printf("%d
", cnt);
82     return 0;
83 }