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

那位大牛帮看一下,通过试例,却总WA,不胜感激

Posted by ZWZ at 2008-03-26 19:46:22 on Problem 3441
//先用动态规划求出第i天到departure day要change的次数;
//再依次求出每次转换的房间;
//通过试例,也通过自己的例子;请那位高手帮忙看看,给个反例也行
#define M 103
#define N 28
#include "iostream"
using namespace std;
int next(int a[M][N],int x,int y,int fin);
int main()
{   int m,n,a[M][N],bol[M],rd[M],rm[M],fin,ini,number[M],cl[M];
        int i,j,k,t,bank=0,cas=1,temp,max;
        char c[M][N];
        char room[M];
        for(room[0]='A',i=1;i<N;i++)
            room[i]=room[i-1]+1;        
        while(1)
        {
                if(bank==1)
                        cout<<endl;
                bank=1;
            cin>>m>>n;
            if(m==0&&n==0)
                        break;
                for(i=0;i<m;i++)
                 cin>>c[i];
                cin>>ini>>fin;
                ini--;fin--;
                for(i=0;i<m;i++)
                {for(j=0,k=0;j<n;j++)
                   if(c[i][j]=='O')
                   {a[i][j]=0;k=1;}
                   else
                        a[i][j]=1;
                 if(k==1)
                         bol[i]=0;
                 else
                         bol[i]=1;
                }
                for(i=ini,k=0;i<fin;i++)
                        if(bol[i]==1)
                        {k=1;break;}
                cout<<"Case "<<cas<<":"<<endl<<endl;
                if(k==1)
                          cout<<"Not available"<<endl;
                else
                {       for(number[fin]=0,number[fin-1]=1,i=fin-2;i>=ini;i--)

                        {for(j=0,k=0,max=-1;j<n;j++)
                                if(a[i][j]==0)
                                 {      temp=next(a,i,j,fin);
                                        if(temp>=fin)
                                            {number[i]=1;k=1;break;}
                                        else if(max<temp)
                                                max=temp;
                                 }
                                
                         if(k==0)
                         number[i]=number[max]+1;        
                        } 
                    for(i=ini;i<fin;)
                       {for(j=0;j<n;j++)
                        if(a[i][j]==0)
                        {temp=next(a,i,j,fin);
                         if(number[temp]==number[i]-1)
                         {cl[i]=j;break;}
                        }
                        i=temp;
                       }                                     
                        for(t=0,i=ini;t<number[ini];t++)
                        {   rd[t]=i;
                                rm[t]=cl[i];
                                i=next(a,i,cl[i],fin);
                        }
                         rd[t]=fin;
                        
                         for(j=0;j<t;j++)
                                cout<<room[rm[j]]<<": "<<rd[j]+1<<"-"<<rd[j+1]
+1<<endl;
                }               
                cas++;          
        }
        return 0;   
}
int next(int a[M][N],int x,int y,int fin)
{  int i;
   for(i=x+1;;i++)
          if(a[i][y]==1||i==fin)
           break;
  return i;
}       

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