CSP-M1-C可怕的宇宙射线

1.题意

宇宙射线会在无限的二维平面上传播（可以看做一个二维网格图），初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的左右45°方向分裂出两条宇宙射线，同时威力不变！宇宙射线会分裂 次，每次分裂后会在分裂方向前进a[i] 个单位长度。求出所经过的位置总数。

2.解题思路

1. 用BFS暴力方法结果在第五个点超时
   思路：如图有8个方向，依次对这8个方向写分裂函数方向1的分裂方向为2和3以此类推，写出8个分裂函数，每分裂一次将同一层的分裂点压到队列中，按层取出分裂点进行分裂
   
2. 用BFS进行剪枝优化
   　　观察其分裂以及前进过程可知若以原点为起始位置，则前进过程中整个前进图关于y轴对称，所以只需考虑右半部分在每次count++时判断该点关于y轴对称的点是否被标记过
   　　通过两个结构体pi,point定义map<pi,int>m来记录该点是否被标记过，map<point,int>m1来标记在该点该方向该分裂次数是否分裂过，因为若分裂过再进行一次得到的结果不变且浪费时间，所以优化每层不重复地到下一层分裂点
   　　通过这两次优化解决TLE问题
3. 用DFS更为凝练的分裂
   　　同理的剪枝优化不重复地分裂，结构体仍相同，优先向右分裂则可得到一个正八边形，以此为规律，则定义两个长度为8的数组dx,dy存储相应的向右分裂x,y的变化点,先向右再向左，该点该方向该分裂次数对应的map为0时分裂，当点未到达时count++，当分裂次数大于n时溯回。
   

4.总结

1. 剪枝优化真的非常有用，但是要思考全面真的很难
2. BFS关于y轴对称优化时，关于判断y轴对称的点是否到达过时，与该点判断是否到达过时，是并行的关系，不能套用
3. 关于BFS/DFS用map与结构体并用来判断该点的该方向该分裂次数是否分裂过时，结构体的重载函数要写全，如果写一半则只要写的相同会认为这两个结构体相同

bool operator<(const point &p) const{
		if(x==p.x)
		{
			if(y==p.y)
			{
				if(z==p.z)
				{
					if(w!=p.w) return w<p.w;
				}
				return z<p.z;
			}
			return y<p.y;
		}
		return x<p.x;
	}
	//而非仅写x,y
		bool operator<(const pi &p) const{
		return x !=p.x ? x<p.x : y<p.y;
	}

5.BFS AC代码

#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
struct point{
	int x;
	int y; 
	int z;
	int w;
	bool operator<(const point &p) const{
		if(x==p.x)
		{
			if(y==p.y)
			{
				if(z==p.z)
				{
					if(w!=p.w) return w<p.w;
				}
				return z<p.z;
			}
			return y<p.y;
		}
		return x<p.x;
	}
};
struct pi{
	int x;
	int y; 
	bool operator<(const pi &p) const{
		return x !=p.x ? x<p.x : y<p.y;
	}
};
queue<point> q;
map<point,int>m1;
map<pi,int>m;
int count=0;
void c1(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.x++;
		p.y++;
		p1.x--;
		p1.y++;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
			
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=3;
	p1.z=2;
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c2(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.y++;
		p1.x--;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
			
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=1;
//	q.push(p);
	p1.z=5;
	//q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c3(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.y++;
		p1.x++;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=1;
//	q.push(p);
	p1.z=4;
//	q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c4(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.x++;
		p.y++;
		p1.x++;
		p1.y--;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
			
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=3;
	//q.push(p);
	p1.z=7;
//	q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c5(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.x--;
		p.y++;
		p1.x--;
		p1.y--;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
			
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=2;
//	q.push(p);
	p1.z=6;
	//q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c6(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.x--;
		p1.y--;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
			
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=5;
//	q.push(p);
	p1.z=8;
//	q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c7(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.x++;
		p1.y--;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=4;
//	q.push(p);
	p1.z=8;
	//q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c8(point &p,int k,int fc)
{
	point p1;
	p1.x=p.x;
	p1.y=p.y;
	for(int i=0;i<k;i++)
	{
		p.x++;
		p.y--;
		p1.x--;
		p1.y--;
		pi p5,p6;
		p5.x=p.x;
		p5.y=p.y;
		p6.x=p1.x;
		p6.y=p1.y;
		if(m[p5]==0) 
		{
			m[p5]=1;
			count++; 
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		}
		if(m[p6]==0) 
		{
			m[p6]=1;
			count++;	
		} 
		pi p4;
		p4.x=-p1.x;
		p4.y=p1.y;
		if(m[p4]==0)
		{
			m[p4]=1;
			count++;
		} 
	}
	p.z=7;
//	q.push(p);
	p1.z=6;
//	q.push(p1);
	p.w=fc+1;
	p1.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
	if(m1[p1]==0)
	{
		q.push(p1);
		m1[p1]=1;
	}
}
void c9(point &p,int k,int fc)
{
	for(int i=0;i<k;i++)
	{
		p.x++;
		p.y++;
		pi p4;
		p4.x=p.x;
		p4.y=p.y;
		if(m[p4]==0) 
		{
			m[p4]=1;
			count++; 
		} 
		pi p3;
		p3.x=-p.x;
		p3.y=p.y;
		if(m[p3]==0)
		{
			m[p3]=1;
			count++;
		} 
	}
	p.z=3;
	//q.push(p);
	p.w=fc+1;
	if(m1[p]==0)
	{
		q.push(p);
		m1[p]=1;
	}
}
void dy(point &p,int k2,int k3)
{
	switch(p.z)
	{
		case 1:
			c1(p,k2,k3);
			break;
		case 2:
			c2(p,k2,k3);
			break;
		case 3:
			c3(p,k2,k3);
			break;
		case 4:
			c4(p,k2,k3);
			break;
		case 5:
			c5(p,k2,k3);
			break;
		case 6:
			c6(p,k2,k3);
			break;
		case 7:
			c7(p,k2,k3);
			break;
		case 8:
			c8(p,k2,k3);
			break;
		case 9:
			c9(p,k2,k3);
			break;
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	point t;
	int *a=new int[n+1];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		if(i==0)
		{
			for(int m1=1;m1<=a[0];m1++)
			{
				t.x=0;
				t.y=m1;
				t.z=0;
				pi t1;
				t1.x=t.x;
				t1.y=t.y;
				m[t1]=1;
				count++;
				if(m1==a[0])
				{
					t.z=9;
					t.w=i;
					q.push(t);
				}
			}
		}
		else
		{
			int m2=q.size();
			for(int m3=0;m3<m2;m3++)
			{
				point p2=q.front();
				q.pop();
				p2.w=i;
				//cout<<p.x<<p.y<<endl;
				//int k=a[i];
				dy(p2,a[i],i);
		
			}	
		}		
	}
	cout<<count<<endl;
	count=0;
	while(!q.empty())
	{
		q.pop();
	}
	return 0;
}

6.DFS AC代码

#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
struct point{
	int x;
	int y; 
	int num;
	int dire;
	point(){
	}
	point(int a,int b,int c,int d){
		x=a;
		y=b;
		num=c;
		dire=d;
	}
	bool operator<(const point &p) const{
		if(x==p.x)
		{
			if(y==p.y)
			{
				if(num==p.num)
				{
					if(dire!=p.dire) return dire<p.dire;
				}
				return num<p.num;
			}
			return y<p.y;
		}
		return x<p.x;
	}

};
struct pi{
	int x;
	int y; 
	bool operator<(const pi &p) const{
		return x !=p.x ? x<p.x : y<p.y;
	}
};
map<pi,int>m1; //到达 
map<point,bool>m2;//分裂 
int count=0,n;
point np,nnp;
int dx[8]={0,1,1,1,0,-1,-1,-1};
int dy[8]={1,1,0,-1,-1,-1,0,1};
int fc[30]={0};
void dfs(point &p)
{
	if(p.num==n)
	{
		return;
	 }
	if(m2[p]==false)
	{
		m2[p]=true;
		for(int i=1;i<=fc[p.num];i++)
		{
			pi p1;
			p1.x=p.x+dx[p.dire]*i;
			p1.y=p.y+dy[p.dire]*i;
			if(m1[p1]==0)
			{
				m1[p1]=1;
				count++;
			}
		}
		int k1=p.x+dx[p.dire]*fc[p.num];
		int k2=p.y+dy[p.dire]*fc[p.num];
		int k3=(p.dire+1)%8;
		int k4=p.num+1;
		point np(k1,k2,k4,k3);
		dfs(np);
		int k5=p.x+dx[p.dire]*fc[p.num];
		int k6=p.y+dy[p.dire]*fc[p.num];
		int k7=(p.dire+7)%8;
		int k8=p.num+1;
		point nnp(k5,k6,k8,k7);
		dfs(nnp);
	}
} 
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>fc[i];
	}
	point p(0,0,0,0);
	dfs(p);
	cout<<count<<endl;
	return 0;
}