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 |
那位大牛帮看一下,通过试例,却总WA,不胜感激//先用动态规划求出第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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator