【Week4 CSP C】可怕的宇宙射线【dfs剪枝】

题意：

宇宙射线会在无限的二维平面上传播（可以看做一个二维网格图），初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的左右45度方向分裂出两条宇宙射线，同时威力不变。宇宙射线会分裂n次(n<=30)，每次分裂后会在分裂方向上前进ai个单位长度(ai<=5)。请输出有多少个位置会被宇宙射线影响到。

思路：

整体思路为dfs剪枝。
首先二维平面使用pointpm类型,记录是否标记与这个坐标经过的射线。射线使用int l[8][31]来记录，第一维为方向（0至7为顺时针的上、右上……），第二维为第几次分裂，内容为分裂长度。
坐标类型为point，包含坐标x，y与方向fx。
接下来是dfs：若是最后一次分裂，只需要将其前进ai格；否则，应先前进ai格，然后分裂出两条射线，然后判断分裂出的射线是否应剪枝，不剪枝则对射线进行dfs。
前进函数应把射线前进ai格，同时在地图上把射线经过的地方进行记录，记录下当前射线的方向以及还要走多长单位距离。
分裂函数，坐标不变，方向更改，根据规定的方向0至7可以轻松算出分裂后的方向。
最后是剪枝部分，需要判断射线当前方向的下一格是否有同一次分裂级数同方向距离减一的标记。若有，则该射线不需要计算分裂，剪枝。

总结：

一道dfs剪枝题，对应CSP T4。 在实验时一个多小时只写了dfs和错误的剪枝，过后才重整思路，写了快一个下午写出来。
剪枝过程：判断射线方向上是否有ai格已经标记（理所当然的WA）->记录射线的方向与长度，没有记录分裂次数（WA，因为可能有两轮射线在同一坐标同方向长度，但后续分裂的前进长度会不同）->记录射线的方向、长度与轮数，但后一次分裂会把轮数覆盖（TLE，剪枝不够多）->最终版本，记录方向、分裂次数与长度。
做题时还纠结了好长时间的内存占用空间，很小气地开了300*300的数组,但其实可以开大亿点点（内存128MB）。
还有计算方向可以使用dx[],dy[]数组来计算，那样更简洁一些，只不过实验时太急，还是用了自己习惯的方式（复制粘贴真香）。

代码：

#include <iostream>
using namespace std;
//每次分裂后根据坐标信息判断是否剪枝
//前一轮与后一轮坐标方向长度都一样也不能剪枝,因为后序分裂的前进长度不同 
//所以要记录第几轮分裂 
//但仅记录一次轮数(后一次分裂会覆盖上一次轮数)会TLE,需要把每次分裂的轮数记录下来 
//应注意128MB内存空间 
struct pointpm
{
	bool biaoji; 
	int l[8][31];	//第一维为方向,第二维为第几次分裂,内容为长度
	pointpm()	//初始化 
	{
		biaoji=0;
		for(int i=0;i<8;i++)
			for(int j=0;j<31;j++)
				l[i][j]=-1;
	}
};
//二维平面 
pointpm pingmian[300][300];
int sum=0;
int n;
struct point
{
	int x,y;
	int fx;//0-7,从上顺时针走起,如0代表上,1代表右上 
};
void getfx(point &p1,point &p2,point &p3)	//p1分裂为p2,p3,坐标不变,更改方向 
{
	if(p1.fx==0)	p2.fx=1,p3.fx=7;
	else if(p1.fx==7)	p2.fx=0,p3.fx=6;
	else p2.fx=p1.fx+1,p3.fx=p1.fx-1;
}
void qianjin(point &p1,int lun,int l)	//p1第lun次分裂前进l长度单位,同时在地图上进行记录 
{	//记录当前射线的方向以及还要走多长单位距离 
	if(p1.fx==0)	//上 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x][p1.y+i].biaoji==0)	//标记 
			{
				pingmian[p1.x][p1.y+i].biaoji=1;
				sum++;
			}
			pingmian[p1.x][p1.y+i].l[0][lun]=l-i;	//前进长度	
		}
		p1.x=p1.x,p1.y=p1.y+l;
	}
	else if(p1.fx==1)	//右上 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x+i][p1.y+i].biaoji==0)
			{
				pingmian[p1.x+i][p1.y+i].biaoji=1;
				sum++;
			}	
			pingmian[p1.x+i][p1.y+i].l[1][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x+l,p1.y=p1.y+l;
	}
	else if(p1.fx==2)	//右 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x+i][p1.y].biaoji==0)
			{
				pingmian[p1.x+i][p1.y].biaoji=1;
				sum++;
			}	
			pingmian[p1.x+i][p1.y].l[2][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x+l,p1.y=p1.y;
	}
	else if(p1.fx==3)	//右下 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x+i][p1.y-i].biaoji==0)
			{
				pingmian[p1.x+i][p1.y-i].biaoji=1;
				sum++;
			}	
			pingmian[p1.x+i][p1.y-i].l[3][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x+l,p1.y=p1.y-l;
	}
	else if(p1.fx==4)	//下 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x][p1.y-i].biaoji==0)
			{
				pingmian[p1.x][p1.y-i].biaoji=1;
				sum++;
			}	
			pingmian[p1.x][p1.y-i].l[4][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x,p1.y=p1.y-l;
	}
	else if(p1.fx==5)	//左下 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x-i][p1.y-i].biaoji==0)
			{
				pingmian[p1.x-i][p1.y-i].biaoji=1;
				sum++;
			}	
			pingmian[p1.x-i][p1.y-i].l[5][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x-l,p1.y=p1.y-l;
	}
	else if(p1.fx==6)	//左 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x-i][p1.y].biaoji==0)
			{
				pingmian[p1.x-i][p1.y].biaoji=1;
				sum++;
			}	
			pingmian[p1.x-i][p1.y].l[6][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x-l,p1.y=p1.y;
	}
	else if(p1.fx==7)	//左上 
	{
		for(int i=1;i<=l;i++)
		{
			if(pingmian[p1.x-i][p1.y+i].biaoji==0)
			{
				pingmian[p1.x-i][p1.y+i].biaoji=1;
				sum++;
			}	
			pingmian[p1.x-i][p1.y+i].l[7][lun]=l-i;	//前进长度 
		} 
		p1.x=p1.x-l,p1.y=p1.y+l;
	}
 } 
bool jianzhi(point &p,int lun,int l)	//要剪枝返回true 
{	//判断当前方向下一格是否有同一次分裂级数同方向距离减一的标记
	if(p.fx==0)
	{
		if(pingmian[p.x][p.y+1].l[0][lun]==l-1)
			return true;
		else return false;
	} 
	else if(p.fx==1)
	{
		if(pingmian[p.x+1][p.y+1].l[1][lun]==l-1)
			return true;
		else return false;
	}
	else if(p.fx==2)
	{
		if(pingmian[p.x+1][p.y].l[2][lun]==l-1)
			return true;
		else return false;
	}
	else if(p.fx==3)
	{
		if(pingmian[p.x+1][p.y-1].l[3][lun]==l-1)
			return true;
		else return false;
	}
	else if(p.fx==4)
	{
		if(pingmian[p.x][p.y-1].l[4][lun]==l-1)
			return true;
		else return false;
	}
	else if(p.fx==5)
	{
		if(pingmian[p.x-1][p.y-1].l[5][lun]==l-1)
			return true;
		else return false;
	}
	else if(p.fx==6)
	{
		if(pingmian[p.x-1][p.y].l[6][lun]==l-1)
			return true;
		else return false;
	}
	else if(p.fx==7)
	{
		if(pingmian[p.x-1][p.y+1].l[7][lun]==l-1)
			return true;
		else return false;
	}
	return false;
 } 
void dfs(point &p1,int i,int *a)
{	//点p1要进行第i次分裂,a[i]为走的单位长度 
	//到n时只需要走a[i],不用再分裂
	if(i==n)
	{
		qianjin(p1,i,a[i]);
		return;
	}
	//先前进a[i]
	qianjin(p1,i,a[i]);
	//分裂
	point p2,p3;
	p2.x=p1.x,p2.y=p1.y,p3.x=p1.x,p3.y=p1.y;
	getfx(p1,p2,p3);
	//分裂后的两条射线继续前进
	if(!jianzhi(p2,i+1,a[i+1]))	//剪枝 
		dfs(p2,i+1,a);
	if(!jianzhi(p3,i+1,a[i+1]))	
		dfs(p3,i+1,a); 
}
int main()
{
	//读入
	cin>>n;
	int *a=new int [n+1];	//从a[1]开始 
	for(int i=1;i<=n;i++)
		cin>>a[i]; 
	//起始点
	point p;
	p.x=150,p.y=150,p.fx=0;	//平面为300*300,从中心开始 
	dfs(p,1,a);
	cout<<sum<<endl; 
	return 0;
}