| ||||||||||
| 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