可怕的宇宙射线

题意：
宇宙射线会在无限的二维平面上传播(可以看做一个二维网格图)，初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的左右45°方向分裂出两条宇宙射线，同时威力不变。宇宙射线会分裂n次，每次分裂后会在分裂方向前进ai 个单位长度。计算出共有多少个位置会被打击。
输入：
输入第一行包含一个正整数n(n <= 30)，表示宇宙射线会分裂n次，第二行包含n个正整数a1,a2…an，第i个数ai(ai <= 5)表示第i次分裂的宇宙射线会在它原方向上继续走多少个单位长度。
输出：
输出一个数ans，表示有多少个位置会被降智打击。
输入样例：
4
4 2 2 3
输出样例：
39
解题思路：
这道题目思路非常清晰，一定可以使用递归完成。于是理清楚思路开始写递归函数solve。solve函数倒是挺容易写出来的，注意用一个数组来存储每一次分裂前行走的路程，一个num用来帮助判断递归结束的条件。然后对每个方向进行分类讨论，往set中插入点的下一个坐标（set可以自动去重复）。这一次分裂前的路程走完了很自然的递归调用solve(cx, cy, (d+7)%8, num+1)与 solve(cx, cy, (d+1)%8, num+1)继续往左右45度角两个方向继续前进，最后只需要输入set的size即可，到此程序完美结束。可惜只能过一半的评测点，另一半会超时。然后我们发现两次递归中其实可以减少一次递归，因为左右是对称的，我们只需要dfs到头再回溯到起点，这个过程中利用对称的性质不断将点对称便可以得到所有点的坐标。无论选择一直向右还是一直向左我们都只需要调用一次solve函数进行递归即可。注意改进后的程序需要首先dfs到头，故要先递归调用一次solve，然后对set中所有点对称，然后再对这一次应该经过的路径加在set中。对称的坐标变换公式很容易由初中数学知识进行推导，总共只有四种对称的情况。
注意事项：
1、按照d（方向参数）分类讨论太傻了，直接用偏移量数组会使程序更简洁一些。
2、如果默认起点坐标为（0，0），那么第一次调用函数应该是solve(0, -1, 0, 1)，因为（0，-1）不会被记录到set中，但这并不妨碍大局。因为图上点的坐标是我们认为指定的，即使使用solve(0, 0, 0, 1)也只是代表图中起点为（0，1）而已，set的size不变，只是具体坐标改变。
总结：
一个dfs的应用题，使用递归求解，注意递归参数和递归结束条件的选择。递归很容易超时，这里发现利用对称性可以减少一次递归从而减少时间复杂度。
参考代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
using namespace std;
int a[40];
set<pair<int, int> > s;
int n;
void solve(int cx,int cy,int d,int num){
    if(num>n)return;
    int x=a[num];
    int x2=cx;int y2=cy;
    if(d==0){
        while (x--) {
            y2++;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==1){
        while (x--) {
            y2++;x2++;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==2){
        while (x--) {
            x2++;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==3){
        while (x--) {
            x2++;y2--;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==4){
        while (x--) {
            y2--;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==5){
        while (x--) {
            y2--;x2--;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==6){
        while (x--) {
            x2--;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    if(d==7){
        while (x--) {
            y2++;x2--;
        }
        solve(x2, y2, (d+7)%8, num+1);
    }
    for (set<pair<int, int> > ::iterator it=s.begin(); it!=s.end(); it++) {
        if(d==0||d==4){
            s.insert(pair<int, int>(2*cx-it->first,it->second));
        }
        if(d==2||d==6){
            s.insert(pair<int, int>(it->first,2*cy-it->second));
        }
        if(d==1||d==5){
            s.insert(pair<int, int>(it->second-cy+cx,cy+it->first-cx));
            }
        if(d==3||d==7){
            s.insert(pair<int, int>(cx+cy-it->second,cy+cx-it->first));
        }
    }
    x=a[num];
    if(d==0){
        while (x--) {
            cy++;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==1){
        while (x--) {
            cy++;cx++;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==2){
        while (x--) {
            cx++;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==3){
        while (x--) {
            cx++;cy--;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==4){
        while (x--) {
            cy--;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==5){
        while (x--) {
            cy--;cx--;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==6){
        while (x--) {
            cx--;
            s.insert(pair<int, int>(cx,cy));
        }
    }
    if(d==7){
        while (x--) {
            cy++;cx--;
            s.insert(pair<int, int>(cx,cy));
        }
    }
}
int main() {
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>a[i];
    }
    solve(0, -1, 0, 1);
    cout<<s.size()<<endl;
    return 0;
}