给出烟花的爆炸方式和爆炸次数 问最后有多少个格子会被炸到
如果dfs的话会超时...
利用模拟每一层来搜索..?
思想就是一开始有一个爆炸点向上 然后模拟完第一段 会产生一个爆炸点 朝两个方向 就用vector来存 每一层都处理一段的爆炸点 产生新一段的爆炸点
因为5*30=150 所以图建300就可以了 300 * 300 * 30的时间复杂度
但是常数很大..不过无所谓啦..
需要注意的是 一个爆炸点可能会同时出现两次朝同一个方向开始爆炸的烟花 这个是没有意义的 所以拿一个数组来记录 不然最后会产生很多情况
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int a[35];
int n;
bool vis[405][405];
int res ;
/// 1 2 3 4 5 6 7 8
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};
vector<int >q[405][405];
vector<int >z[405][405];
bool cz[405][405][8];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
memset(vis,true,sizeof(vis));
for(int i = 0;i<=402;i++){
for(int j = 0;j<= 402;j++){
q[i][j].clear();
}
}
for(int i = 0;i<=402;i++){
for(int j = 0;j<= 402;j++){
z[i][j].clear();
}
}
res = 0;
q[200][200].push_back(0);
memset(cz,false,sizeof(cz));
for(int w = 1;w <= n ;w ++){
for(int i = 1;i<=400;i++){
for(int j = 1;j<=400;j++){
for(int l = 0; l< q[i][j].size();l ++){
for(int k = 1;k<=a[w];k++){
if(vis[k*dx[q[i][j][l]] + i][k*dy[q[i][j][l]] + j] == true)
vis[k*dx[q[i][j][l]] + i][k*dy[q[i][j][l]] + j] = false,res ++ ;
}
int fx1 = q[i][j][l] + 1; fx1 += 8; fx1 %= 8;
int fx2 = q[i][j][l] - 1; fx2 += 8; fx2 %= 8;
if(cz[a[w]*dx[q[i][j][l]] + i][a[w]*dy[q[i][j][l]] + j][fx1] == false)
z[a[w]*dx[q[i][j][l]] + i][a[w]*dy[q[i][j][l]] + j].push_back(fx1),cz[a[w]*dx[q[i][j][l]] + i][a[w]*dy[q[i][j][l]] + j][fx1] = true;
if(cz[a[w]*dx[q[i][j][l]] + i][a[w]*dy[q[i][j][l]] + j][fx2] == false)
z[a[w]*dx[q[i][j][l]] + i][a[w]*dy[q[i][j][l]] + j].push_back(fx2),cz[a[w]*dx[q[i][j][l]] + i][a[w]*dy[q[i][j][l]] + j][fx2] = true;
}
q[i][j].clear();
}
}
for(int i = 1;i<=400;i++){
for(int j = 1 ;j<=400;j++){
for(int l = 0;l < z[i][j].size();l ++){
q[i][j].push_back(z[i][j][l]);
}
z[i][j].clear();
}
}
memset(cz, false, sizeof(cz));
}
printf("%d\n",res);
}