Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

高手,思路很妙啊,借鉴思路了

Posted by stupidjohn at 2011-01-25 17:59:17 on Problem 1104
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator