POJ 3414——Bfsベーステンプレートコード
2392 ワード
Program poj3414;//By_Thispoet
Const
maxn=100;
Var
v :Array[0..maxn,0..maxn]of Boolean;
h,t,p,q :Longint;
a,b,c,i,j :Longint;
seq :Array[1..maxn*maxn*10]of record l,r,fa,did:Longint;end;
ans :Array[0..maxn*maxn]of Longint;
flag :Boolean;
Function Check(i:Longint):Boolean;
begin
if (seq[i].l=c)or(seq[i].r=c) then
begin
flag:=true;
exit(true);
end;
exit(false);
end;
Function Min(i,j:Longint):Longint;
begin
if i<j then exit(i);exit(j);
end;
Procedure Printf();
begin
writeln(ans[0]);
while ans[0]>0 do
begin
case ans[ans[0]] of
1:writeln('FILL(1)');
2:writeln('FILL(2)');
3:writeln('DROP(1)');
4:writeln('DROP(2)');
5:writeln('POUR(2,1)');
6:writeln('POUR(1,2)');
end;
dec(ans[0]);
end;
end;
BEGIN
readln(a,b,c);
fillchar(v,sizeof(v),0);
h:=0;t:=1;seq[1].l:=0;seq[1].r:=0;
seq[1].fa:=0;flag:=false;
while h<t do
begin
inc(h);
i:=seq[h].l;j:=seq[h].r;
if not v[a,j] then
begin
v[a,j]:=true;
inc(t);
seq[t].l:=a;seq[t].r:=j;
seq[t].fa:=h;seq[t].did:=1;
end;
if check(t) then break;
if not v[i,b] then
begin
v[i,b]:=true;
inc(t);
seq[t].l:=i;seq[t].r:=b;
seq[t].fa:=h;seq[t].did:=2;
end;
if check(t) then break;
if not v[0,j] then
begin
v[0,j]:=true;
inc(t);
seq[t].l:=0;seq[t].r:=j;
seq[t].fa:=h;seq[t].did:=3;
end;
if check(t) then break;
if not v[i,0] then
begin
v[i,0]:=true;
inc(t);
seq[t].l:=i;seq[t].r:=0;
seq[t].fa:=h;seq[t].did:=4;
end;
if check(t) then break;
p:=Min(a,i+j);q:=i+j-p;
if not v[p,q] then
begin
v[p,q]:=true;
inc(t);
seq[t].l:=p;seq[t].r:=q;
seq[t].fa:=h;seq[t].did:=5;
end;
if check(t) then break;
q:=Min(b,i+j);p:=i+j-q;
if not v[p,q] then
begin
v[p,q]:=true;
inc(t);
seq[t].l:=p;seq[t].r:=q;
seq[t].fa:=h;seq[t].did:=6;
end;
end;
if not flag then writeln('impossible')else
begin
fillchar(ans,sizeof(ans),0);
while t>1 do
begin
inc(ans[0]);
ans[ans[0]]:=seq[t].did;
t:=seq[t].fa;
end;
printf();
end;
END.