Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
高手,思路很妙啊,借鉴思路了In Reply To:想自虐,一个地方把i写成1WA了N多次,附AC代码 Posted by:yzhw at 2009-04-18 09:20:55 > # include <stdio.h> > # include <stdbool.h> > int w,h,t; > struct refer > { > int t; > int lx,ly; > int rx,ry; > }data[105]; > struct point > { > int x,y; > int t; > }res[105],resfinal[105]; > bool map[105][101][101]; > int len[101]; > int num; > void setmap1(int now,int lx,int ly,int rx,int ry) > { > if(rx>=lx&&ry>=ly&&now<=t+1&&now>=1) > { > int i,j; > for(i=lx;i<=rx;i++) > for(j=ly;j<=ry;j++) > map[now][i][j]=0; > setmap1(now+1,lx+1,ly+1,rx-1,ry-1); > } > else return; > } > void setmap2(int now,int lx,int ly,int rx,int ry) > { > if(rx>=lx&&ry>=ly&&now<=t+1&&now>=1) > { > int i,j; > for(i=lx;i<=rx;i++) > for(j=ly;j<=ry;j++) > map[now][i][j]=0; > setmap2(now-1,lx+1,ly+1,rx-1,ry-1); > } > else return; > } > bool reset1(int now) > { > bool flag=0; > int i,j,tlen=0,tx,ty; > for(i=1;i<=w;i++) > for(j=1;j<=h;j++) > if(map[now][i][j]) > { > if((map[now-1][i][j])||(map[now-1][i+1][j]&&i+1<=w)||(map[now-1][i-1][j]&&i-1>=1)||(map[now-1][i][j+1]&&j+1<=h)||(map[now-1][i][j-1]&&j-1>=1)) > { > tlen++; > tx=i; > ty=j; > } > else > { > map[now][i][j]=0; > flag=1; > } > } > len[now]=tlen; > if(tlen==1) > { > res[now].x=tx; > res[now].y=ty; > } > return flag; > } > bool reset2(int now) > { > bool flag=0; > int i,j,tlen=0,tx,ty; > for(i=1;i<=w;i++) > for(j=1;j<=h;j++) > if(map[now][i][j]) > { > if((map[now+1][i][j])||(map[now+1][i+1][j]&&i+1<=w)||(map[now+1][i-1][j]&&i-1>=1)||(map[now+1][i][j+1]&&j+1<=h)||(map[now+1][i][j-1]&&j-1>=1)) > { > tlen++; > tx=i; > ty=j; > } > else > { > map[now][i][j]=0; > flag=1; > } > } > len[now]=tlen; > if(tlen==1) > { > res[now].x=tx; > res[now].y=ty; > } > return flag; > } > int main() > { > int casenum=1; > while(1) > { > scanf("%d %d %d",&w,&h,&t); > memset(map,1,sizeof(map)); > memset(len,0,sizeof(len)); > if(!w&&!h&&!t) break; > int i,j; > scanf("%d",&num); > for(i=1;i<=num;i++) > { > scanf("%d %d %d %d %d",&data[i].t,&data[i].lx,&data[i].ly,&data[i].rx,&data[i].ry); > } > /*-------------------buildmap----------------------------------*/ > for(i=1;i<=num;i++) > { > setmap1(data[i].t,data[i].lx,data[i].ly,data[i].rx,data[i].ry); > setmap2(data[i].t,data[i].lx,data[i].ly,data[i].rx,data[i].ry); > > } > bool flag; > while(1) > { > > flag=0; > for(i=2;i<=t;i++) > { > if(reset1(i)) flag=1; > } > for(i=t;i>=1;i--) > { > if(reset2(i)) flag=1; > } > if(!flag) break; > } > /*-------------------judge-------------------------------------*/ > int count=0; > flag=1; > for(i=1;i<=t;i++) > { > if(len[i]==0) > { > flag=0; > break; > } > else if(len[i]==1) > { > resfinal[++count]=res[i]; > resfinal[count].t=i; > } > } > printf("Robbery #%d:\n",casenum++); > if(!flag) printf("The robber has escaped.\n\n"); > else if(!count) printf("Nothing known.\n\n"); > else > { > for(i=1;i<=count;i++) > printf("Time step %d: The robber has been at %d,%d.\n",resfinal[i].t,resfinal[i].x,resfinal[i].y); > printf("\n"); > } > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator