http://acm.hdu.edu.cn/showproblem.php?pid=4739
这题是dfs，只需一个一个搜就可以了
#include<stdio.h> #include<math.h> #include<stdlib.h> struct node { int x,y; }s[50]; int N,ans,v[50]; int cmp(const void *a,const void *b) { struct node *c=(struct node *)a; struct node *d=(struct node *)b; if(c->y==d->y) return c->x>d->x; else return c->y>d->y; } void dfs(int num,int sum)/*num记录点的位置，sum记录总共可以移动的地雷数量*/ { int i,j,cut,n1,n2; if(ans<sum)ans=sum; for(i=num;i<N;i++) { if(v[i])continue; v[i]=1; for(j=i+1;j<N;j++) { if(v[j]||s[i].x!=s[j].x||s[i].y==s[j].y) continue; v[j]=1; cut=abs(s[j].y-s[i].y); for (n1=0;n1<N;n1++) if (s[n1].x==s[i].x+cut && s[n1].y==s[i].y && !v[n1]) break;//找到对应的那个是否存在 if (n1==N) { v[j]=0; continue; } v[n1]=1; for (n2=0;n2<N;n2++) if (s[n2].x==s[j].x+cut && s[n2].y==s[j].y && !v[n2]) break; if (n2==N) { v[j]=v[n1]=0; continue; } v[n2]=1; dfs(i+1,sum+4); v[j]=v[n1]=v[n2]=0; } v[i]=0; } } int main() { int i,j; struct node temp; while(scanf("%d",&N),N!=-1) { for(i=0;i<N;i++) v[i]=0; for(i=0;i<N;i++) scanf("%d%d",&s[i].x,&s[i].y); /*qsort(s,N,sizeof(s[0]),cmp);*/ /*for(i=0;i<N-1;i++) { for(j=i;j<N-1;j++) if(s[j].y>s[j+1].y) temp=s[j],s[j]=s[j+1],s[j+1]=temp; else if(s[j].y==s[j+1].y&&s[j].x>s[j+1].x) temp=s[j],s[j]=s[j+1],s[j+1]=temp; }*/ /*for(i=0;i<N;i++) printf("(%d,%d) ",s[i].x,s[i].y);*/ ans=0; dfs(0,0); printf("%d ",ans); } return 0; }