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 c0500448264 at 2005-06-30 21:39:55 on Problem 2458
In Reply To:大牛们能不能帮我看看这个程序为什么tle?我怎么算来复杂度都没那么高啊…… Posted by:wangchen1ren at 2005-06-30 21:35:44
> #include <iostream>
> #include <string.h>
> using namespace std;
> 
> char s[5][5];
> bool flag[5][5];
> long tot=0;
> 
> bool connect()
> {
>     static int dx[4]={0,1,0,-1};
>     static int dy[4]={1,0,-1,0};
>     bool boolean[5][5];
>     int px[10],py[10],h,l,x,y;
>     memset(boolean,false,sizeof(boolean));
>     for(int i=0;i<25;i++)
>       if (flag[i/5][i%5])
>       {
>           boolean[i/5][i%5]=true;
>           h=0;l=1;
>           px[0]=i/5;py[0]=i%5;
>           while (h<l)
>           {
>               for(int j=0;j<4;j++)
>               {
>                   x=px[h]+dx[j];y=py[h]+dy[j];
>                   if (flag[x][y]&&x>=0&&x<5&&y>=0&&y<5&&!boolean[x][y])
>                   {
>                       px[l]=x;py[l]=y;
>                       boolean[x][y]=true;
>                       l++;
>                   }
>               }
>               h++;
>           }
>           if (l>=7) return true;
>           else return false;
>       }
> }    
> 
> bool overnum()
> {
>     int i,t=0;
>     for(i=0;i<25;i++)
>       if (flag[i/5][i%5]&&s[i/5][i%5]=='J')
>         t++;
>     if (t>3) return true;
>     else return false;
> }    
> 
> void work()
> {
>     int i[8],j;
>     for(i[1]=0;i[1]<25-6;i[1]++)
>       for(i[2]=i[1]+1;i[2]<25-5;i[2]++)
>         for(i[3]=i[2]+1;i[3]<25-4;i[3]++)
>           for(i[4]=i[3]+1;i[4]<25-3;i[4]++)
>             for(i[5]=i[4]+1;i[5]<25-2;i[5]++)
>               for(i[6]=i[5]+1;i[6]<25-1;i[6]++)
>                 for(i[7]=i[6]+1;i[7]<25;i[7]++)
>                 {
>                     for(j=1;j<=7;j++)
>                       flag[i[j]/5][i[j]%5]=true;
>                     if (connect()&&overnum()) tot++;
>                     for(j=1;j<=7;j++)
>                       flag[i[j]/5][i[j]%5]=false;
>                 }        
> }
> 
> main()
> {
> //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
>     for(int i=0;i<5;i++)
>       scanf("%s",s[i]);
>     memset(flag,false,sizeof(flag));
>     work();
>     printf("%d\n",tot);
> } 

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