Good Bye 2016 D. New Year and Fireworks BFS

D. New Year and Fireworks

链接：

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

题解：

vis[i][j][k][l]用来记录在 (i,j)这个点在第k次爆炸中在l方向有没有被访问过

访问过就continue 这样就不会超时了其他的就是bfs了

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstring>
10 #include <iostream>
11 #include <algorithm>
12 #include <functional>
13 using namespace std;
14 #define rep(i,a,n) for (int i=a;i<=n;i++)
15 #define per(i,a,n) for (int i=n;i>=a;i--)
16 #define pb push_back
17 #define mp make_pair
18 #define all(x) (x).begin(),(x).end()
19 #define fi first
20 #define se second
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll mod = 1e9 + 7;
26 const int inf = 0x3f3f3f3f;
27 const double eps = 1e-7;
28 // head
29 
30 struct Point {
31     int x, y;
32     int i;
33     int dir;
34 };
35 map<PII, int> mm; 
36 int vis[400][400][40][8];
37 int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
38 int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
39 int n;
40 int t[50];
41 int ans;
42 
43 void bfs() {
44     rep(i, 0, t[1] - 1) mm[PII(200, 200 + i)] = 1;
45     ans += t[1];
46     queue<Point> mq;
47     Point k;
48     k.x = 200, k.y = 200 + t[1] - 1, k.i = 1, k.dir = 2;
49     mq.push(k);
50     while (!mq.empty()) {
51         k = mq.front();
52         mq.pop();
53         if (k.i == n) continue;
54         if (vis[k.x][k.y][k.i][k.dir]) continue;
55         else vis[k.x][k.y][k.i][k.dir] = 1;
56         Point p = k;
57         int d = (k.dir + 7) % 8;
58         rep(i, 1, t[k.i + 1]) {
59             p.x += dx[d];
60             p.y += dy[d];
61             if (!mm[PII(p.x, p.y)]) mm[PII(p.x, p.y)] = 1, ans++;
62         }
63         p.i++;
64         p.dir = d;
65         mq.push(p);
66         p = k;
67         d = (k.dir + 1) % 8;
68         rep(i, 1, t[k.i + 1]) {
69             p.x += dx[d];
70             p.y += dy[d];
71             if (!mm[PII(p.x, p.y)]) mm[PII(p.x, p.y)] = 1, ans++;
72         }
73         p.i++;
74         p.dir = d;
75         mq.push(p);
76     }
77 }
78 
79 int main() {    
80     cin >> n;
81     rep(i, 1, n) cin >> t[i];
82     bfs();
83     cout << ans << endl;
84     return 0;
85 }