bfs或者dfs Good Bye 2016 D

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

题目大意:

放鞭炮,鞭炮会爆炸n次,每次只会往目前前进方向的左上和右上放出他的子鞭炮。问,最后能有多少格子被覆盖?

思路:

感觉是期末复习阶段太久没有敲代码了的缘故吧,记忆化搜索的状态找的都不准确了。

bfs,然后定义dp(x,y,z,dir)表示在(x,y)这个位置,第z次爆炸,爆炸方向为dir。如果这个状态存在,就不放入队列。

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
/*
定义:dp(x, y, t, dir = 8),当前在坐标(x, y)这个位置,朝向为dir,将要从这点开始走t步(假定,向上是+,向下是-.),是否走过这个状态
*/
const int maxpos = + ;
int dp[maxpos][maxpos][][];
int color[maxpos][maxpos];
int n;
int t[maxpos];
pair<int, int> dir[]; void init(){
cin >> n;
for (int i = ; i <= n; i++){
scanf("%d", t + i);
}
///逆时针标号
dir[] = mk(, ), dir[] = mk(, ), dir[] = mk(-, ), dir[] = mk(-, );
dir[] = mk(-, -), dir[] = mk(, -), dir[] = mk(, -), dir[] = mk(, );
} struct Point{
int x, y, aim;
}; int bfs(){
if (n == ) return t[];
t[n + ] = ;
int x = , y = ;
//dp[x][y + 1][t[1] - 1][1] = 1;
queue<Point> que;
for (int i = ; i <= t[]; i++){
int nx = dir[].fi + x, ny = dir[].se + y;
color[nx][ny] = ;
x = nx, y = ny;
}
//printf("x = %d y = %d\n", x, y);
que.push(Point{x, y, });
que.push(Point{x, y, });
dp[x][y][][] = ;
dp[x][y][][] = ;
for (int i = ; i <= n; i++){
queue<Point> tmp;
while (!que.empty()){
Point from = que.front(); que.pop();
//printf("%d %d\n", from.x, from.y);
for (int j = ; j <= t[i]; j++){
int nx = from.x + dir[from.aim].fi, ny = from.y + dir[from.aim].se;
color[nx][ny] = ;
from.x = nx, from.y = ny;
//printf("nx = %d ny = %d\n", nx, ny);
}
int lb = (from.aim + ) % , rb = (from.aim - + ) % ;
if (dp[from.x][from.y][i][lb] == ){
tmp.push(Point{from.x, from.y, lb});
dp[from.x][from.y][i][lb] = ;
}
if (dp[from.x][from.y][i][rb] == ){
tmp.push(Point{from.x, from.y, rb});
dp[from.x][from.y][i][rb] = ;
}
}
que = tmp;
}
int ans = ;
for (int i = ; i < ; i++){
for (int j = ; j < ; j++){
ans += color[i][j];
//if (color[i][j]) printf("x = %d y = %d\n", i, j);
}
}
return ans;
} int main(){
init();
printf("%d\n", bfs());
return ;
}
上一篇:Conclusion


下一篇:cesium 之三维漫游飞行效果实现篇(附源码下载)