首页 > 代码库 > codeforces 750D New Year and Fireworks【DFS】
codeforces 750D New Year and Fireworks【DFS】
题意：烟花绽放时分为n层，每层会前进ti格，当进入下一层是向左右45°分开前进。 问在网格中，有多少网格至少被烟花经过一次？
题解：最多30层，每层最多前进5格，烟花的活动半径最大为150，每一层的方向都可以由上一层决定，所以一定 小于300*300中情况，直接暴力绽放的过程就行了。bfs和dfs都可以做。
dfs：
#include<stdio.h>#include<iostream>#include<math.h>#include<algorithm>#include<string>typedef long long ll;#define MAXN 100000using namespace std;int n, a[35], m[305][305], vis[35][305][305][8];//clockwiseint dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };int dy[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };void dfs(int cur, int x, int y, int dir){ if (cur == n || vis[cur][x][y][dir]) return; vis[cur][x][y][dir] = m[x][y] = 1; for (int i = 1; i < a[cur]; i++) { x += dx[dir]; y += dy[dir]; m[x][y] = 1; } int nd = (dir + 1) & 7; dfs(cur + 1, x + dx[nd], y + dy[nd], nd); nd = (dir + 7) & 7; dfs(cur + 1, x + dx[nd], y + dy[nd], nd);}int main(){ cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } dfs(0, 150, 150, 4); int cnt = 0; for (int i = 0; i < 305; i++) { for (int j = 0; j < 305; j++) { if (m[i][j]) cnt++; } } cout << cnt << endl; return 0;}bfs：
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int maxn = 310; int mark[maxn][maxn][32][6]; int n,a[32],map[maxn][maxn]; int asp[][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; struct node { int x,y,cnt,dir; //cnt：烟花的层数 dir：烟花前进的方向 }temp; void bfs() { queue<node> q; temp.x=150; temp.y=150; temp.cnt=1; temp.dir=0; q.push(temp); mark[150][150][1][0]=1; while(!q.empty()) { temp=q.front(); q.pop(); int nx=temp.x, ny=temp.y, num=temp.cnt, k=temp.dir; for(int i=1;i<=a[num];++i)//当前层走的路径 { nx+=asp[k][0]; ny+=asp[k][1]; map[nx][ny]=1; } if(num!=n) { int kl=(k-1+8)%8, kr=(k+1)%8;//当前烟花炸裂后，分开的两个子烟花前进的方向 temp.x=nx; temp.y=ny; temp.cnt=num+1; if(!mark[nx][ny][num+1][kl])//kl左45° { mark[nx][ny][num+1][kl]=1; temp.dir=kl; q.push(temp); } if(!mark[nx][ny][num+1][kr])//kr右45° { mark[nx][ny][num+1][kr]=1; temp.dir=kr; q.push(temp); } } } int ans=0; for(int i=0;i<=300;++i) for(int j=0;j<=300;++j) if(map[i][j]) ans++; printf("%d\n",ans); } int main() { while(scanf("%d",&n)!=EOF) { memset(map,0,sizeof(map)); memset(mark,0,sizeof(mark)); for(int i=1;i<=n;++i) scanf("%d",&a[i]); bfs(); } return 0; }codeforces 750D New Year and Fireworks【DFS】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。