7th_D

这是一道稍微有点难度的模拟题，通过模拟实际运行的情况，通过队列进行宽搜，重点在于判断齿轮会不会卡住，最后得出结论。
1.算法
(1)预处理：
将所有的齿轮坐标和半径读取，保存在x,y,r三个数组中，然后进行相切判断，两两进行判断，将结果放置在map中，map[i][0]表示有几个齿轮和第i个齿轮相切，map[i][1～x]分别表示和第i个齿轮相切的x个齿轮的号码。
(2)操作：
依次对1～n中的每一个齿轮做检查，判断如果将该齿轮去掉能不能成功。检查操作如下：
从1号齿轮开始，根据map中的相切情况，依次向后进行宽搜，直到搜索到最后一个目标齿轮。
在这个过程中需要注意的是判断齿轮是否会卡住，这里采用齿轮的index(index表示该齿轮是第几个从动齿轮)来判断，比如，1号齿轮index是1，1号齿轮与2号3号分别相切，那2号和3号齿轮的index都是2，如此依次往后，index在队列中存储。当要在队列中加一个齿轮时，要先对队列当前齿轮进行一次遍历，如果发现这个齿轮已经在队列中就不要添加，并判断当前的index和该齿轮在队列中的index，如果两者差是奇数，则齿轮被卡住，该检查失败，返回(想想为什么)。
2.实现
(1)对于队列的操作要注意下标的表示不能太长，可以新建另一个变量保存其值，然后让这个对象作为下标，太长的下标会使得程序看起来很混乱。
(2)注意对于边界值0的处理
(3)在时间足够的情况下可以考虑穷举法解题。

#include<cstdio>
#include<cmath>
int n;
double x[1000];
double y[1000];
double r[1000];

int map[1000][1000];//map[1][0] means the 1st have how many nears;



bool near(int i,int j){
	float dis_mul = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
	float dis_r = r[i]+r[j];
	if(dis_mul <= dis_r)return true;
	else return false;
}
void prework(){
	for(int i=1;i<=n;i++)
		map[i][0]=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf",&(x[i]),&(y[i]),&(r[i]));
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(near(i,j)){
				map[i][++map[i][0]] = j;
				map[j][++map[j][0]] = i;
			}
		}
	}
}

bool check(int x){
	int result=false;
	struct unit{
		int id;
		int index;
	};
	unit queue[1000];
	int p=0,q=1;
	queue[0].id=1;
	queue[0].index=1;
	while(p!=q){
		for(int i=1;i<=map[queue[p].id][0];i++){
			unit temp;
			temp.id = map[queue[p].id][i];
			temp.index=queue[p].index+1;
			if(temp.id!=x){
				bool flag = true;
				for(int j=0;j<q;j++){
					if(queue[j].id==temp.id){
						if((temp.index-queue[j].index)%2==1){
							return false;
						}
						flag=false;
					}
				}
				if(flag){
					queue[q].id=temp.id;
					queue[q].index=temp.index;
					if(queue[q].id==n){
						result=true;
					}
					q++;
				}
			}
		}
		p++;
	}
	return result;
}
int main(){
	prework();
//	for(int i=1;i<=n;i++){
//		printf("%d\n",map[i][0]);
//		for(int j=1;j<=map[i][0];j++){
//			printf(" %d",map[i][j]);
//		}
//		printf("\n");
//	}
	bool done=false;
	if(check(0)){
		printf("0\n");
		done=true;
	}
	for(int i=1;i<=n&&!done;i++){
		if(check(i)){
			printf("%d\n",i);
			done=true;
		}
	}
	if(!done){
		printf("-1\n");
	}
	return 0;
}