poj 3414 Pots
17365 단어 poj
http://poj.org/problem?id=3414
while(scanf("%d%d%d",&A,&B,&C)!=EOF)
Output Limit Exceeded
#include<iostream>
#include<string>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<map>
using namespace std;
const int N=100001;
int go[6]={-1,-2,-3,1,2,3};
int a[N];
int b[N];
int pre[N];
int type[N];
bool had[105][105];
int I,K,J;
int anstype[N];
int ans,nd;
int A,B,C;
bool ok(int a1,int b1,int i)
{
//cout<<a1<<" "<<b1<<" "<<i<<endl;
int l1,l2;
if(i==-1)
{
l1=A;l2=b1;
}else
if(i==-2)
{
l1=0;l2=b1;
}else
if(i==-3)
{
l1=min(A,a1+b1);l2=max(0,a1+b1-A);
}else
if(i==1)
{
l1=a1;l2=B;
}else
if(i==2)
{
l1=a1;l2=0;
}else
{
l2=min(B,a1+b1);l1=max(0,a1+b1-B);
}
if(had[l1][l2])
return false;
had[l1][l2]=true;
type[J]=i;
pre[J]=I;
//cout<<l1<<" "<<l2<<endl;
a[J]=l1;b[J]=l2;++J;
if(l1==C||l2==C)
return true;
return false;
}
void bfs(int k)
{//cout<<k<<endl;
if(K==J)
return;
K=J;
for(;I<K;++I)
{
for(int i=0;i<6;++i)
if(ok(a[I],b[I],go[i]))
{
ans=k;nd=J-1;
return;
}
}
bfs(k+1);
}
void print()
{
int i=ans;
int l=nd;
while(l!=0)
{
anstype[i]=type[l];
l=pre[l];
--i;
}
for(i=1;i<=ans;++i)
{
if(anstype[i]==-1)
printf("FILL(1)
");
if(anstype[i]==-2)
printf("DROP(1)
");
if(anstype[i]==-3)
printf("POUR(2,1)
");
if(anstype[i]==1)
printf("FILL(2)
");
if(anstype[i]==2)
printf("DROP(2)
");
if(anstype[i]==3)
printf("POUR(1,2)
");
}
}
int main()
{
scanf("%d%d%d",&A,&B,&C);
memset(had,false,sizeof(had));
had[0][0]=true;
a[0]=0;b[0]=0;
pre[0]=0;
type[0]=0;
I=K=0;J=1;
ans=-1;
bfs(1);
if(ans==-1)
{
printf("impossible
");
}
else
{
printf("%d
",ans);
print();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.