Giroro的地雷测试

Description

为了早日完成侵略蓝星的使命，Giroro最近新入手了一批地雷。为了测试地雷的可爆性（旁白：有这性质的？），Giroro在一些地方埋下了地雷，并让Tamama射出Tamama冲击波来引爆这些地雷。因为Tamama冲击波的威力是很大的，所以在距离Tamama冲击波距离不大于d的地雷都会爆炸。当一个地雷爆炸时，在这个地雷的爆炸范围内的地雷也会被引爆，而且地雷的爆炸半径各不相同。Giroro迫切想知道被引爆的地雷有多少个！一支大炮直接指向了Tamama…可怜的Tama仔只好找你解决这个问题了。
XxX_Stu帮忙把问题抽象成了计算机问题，描述如下：给点n个地雷的坐标，都为整数坐标，以及它们的爆炸半径。然后给定Tamama发射的纵坐标，以及d也是整数，默认Tamama站在世界的最左端面向世界的最右端水平向右发射冲击波，而且你可以认为Tamama冲击波是无限长的。
图示如下:

讯享网

Input

数据有多组。读入直到文件结束。
对于每组数据：第1行，3个整数n，y，d。表示n个地雷，Tamama冲击波的纵坐标y，冲击波的波及范围d。接下来n行，每行3个整数xi，yi，ri。表示每个地雷的坐标和爆炸半径。0<=n<=200 ; 0<=y , d ,xi , yi , ri <=1000 .

Output

对于每组数据，输出一个整数。即地雷爆炸的个数。

Sample Input

1 1 2 1 2 2 2 1 1 1 1 5 1 3 1 

Sample Output

讯享网1 2 

Source

/* ---------------------------------------------------------------------- 大概思路：因为这一道题的情况是这样的，假设有ABCDEF个地雷，A可能引爆C，C 又可能引爆E，E又有可能回头引爆B，B再引爆F这样子。。所以一般的遍历可能会出错 ，又或者可能会超时。所以这里用广度优先搜索。。自己构造了一个队列。。不是循环 队列的说，怕出错。。 状况：15MS ---------------------------------------------------------------------- */ #include<stdio.h> #include<math.h> #include<memory.h> int a[202][4] ; int BombQueue[205] ; int main(void) { int i = 0 ; int j = 0 ; int n = 0 ; int y = 0 ; int d = 0 ; int k = 0 ; int nVecLen = 0 ; int nIBob = 0 ; int nJBob = 0 ; int nTotal = 0 ; int nHead = 0 ; int nLen = 0 ; int nNowBomb = 0 ; while(scanf("%d%d%d",&n,&y,&d) != EOF) { nTotal = 0 ; memset(a,0,sizeof(a)) ; memset(BombQueue,0,sizeof(BombQueue)) ; nHead = 0 ; nLen = 0 ; for(i = 0 ; i < n ; ++i) { scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]) ; } for(i = 0 ; i < n ; ++i) { if(d >= abs(a[i][1]-y)) { a[i][3] = 1 ; nTotal++ ; BombQueue[nLen] = i ; nLen++ ; } } while(nLen != 0) { nNowBomb = BombQueue[0] ; nLen-- ; for(k = 0 ; k < nLen ; ++k) { BombQueue[k] = BombQueue[k+1] ; } nLen = k ; for(i = 0 ; i < n ; ++i) { if(i == nNowBomb) { continue ; } nVecLen = (a[i][0]-a[nNowBomb][0])*(a[i][0]-a[nNowBomb][0]) + (a[i][1]-a[nNowBomb][1])*(a[i][1]-a[nNowBomb][1]) ; nIBob = a[nNowBomb][2]*a[nNowBomb][2] ; if(0 == a[i][3] && nVecLen <= nIBob) { nTotal++ ; a[i][3] = 1 ; BombQueue[nLen] = i ; nLen++ ; } } } printf("%d\n",nTotal) ; } return 0 ; } 

讯享网错解

#include<stdio.h> #include<math.h> int a[202][4] ; int main(void) { int i = 0 ; int j = 0 ; int n = 0 ; int y = 0 ; int d = 0 ; int nVecLen = 0 ; int nIBob = 0 ; int nJBob = 0 ; int nTotal = 0 ; while(scanf("%d%d%d",&n,&y,&d) != EOF) { nTotal = 0 ; for(i = 0 ; i < n ; ++i) { scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]) ; } for(i = 0 ; i < n ; ++i) { if(d >= abs(a[i][1]-y)) { a[i][3] = 1 ; //表示已经被激光射中，会爆 nTotal++ ; } } for(i = 0 ; i < n ; ++i) { for(j = 0 ; j < n ; ++j) { if(i == j) { continue ; } nVecLen = (a[i][0]-a[j][0])*(a[i][0]-a[j][0]) + (a[i][1]-a[j][1])*(a[i][1]-a[j][1]) ; nIBob = a[i][2]*a[i][2] ; nJBob = a[j][2]*a[j][2] ; if(1 == a[i][3] && 0 == a[j][3] && nVecLen <= nIBob) { nTotal++ ; a[j][3] = 1 ; } else if(0 == a[i][3] && 1 == a[j][3] && nVecLen <= nJBob) { nTotal++ ; a[i][3] = 1 ; } } } printf("%d\n",nTotal) ; } return 0 ; }