POJ 3414 Pots

問題

容量AリットルとBリットルの二つの容器がある。
以下の操作を繰り返してどちらかの容器に入っている水の量をCリットルする。
最短手順の操作をどれか一つ出力せよ。
不可能な場合impossibleを出力せよ。

• Aの容器を満タンにする
• Bの容器を満タンにする
• Aの容器に入っている水を全て捨てる
• Aの容器に入っている水を全て捨てる
• Aの容器からBの容器に水を移す。移し終わった後、Aが空になっているか、Bが満タンになっていなければならない。
• Bの容器からAの容器に水を移す。移し終わった後、Bが空になっているか、Aが満タンになっていなければならない。

制約条件

A,B≦100
C≦max(A,B)

方針

幅優先探索+経路復元。

ソースコード

int A,B,C;
int prev[101][101],op[101][101];
int ans[11000], sz;

int main(){
  memset(prev,-1,sizeof(prev));
  scanf("%d%d%d",&A,&B,&C);
  queue<int> q;
  q.push(0);
  while(!q.empty()){
    int a=q.front()/101, b=q.front()%101; q.pop();
    if(a==C||b==C){
      for(;a||b;){
        ans[sz++]=op[a][b];
        int na=prev[a][b]/101, nb=prev[a][b]%101;
        a=na; b=nb;
      }
      reverse(ans,ans+sz);
      printf("%d\n",sz);
      rep(i,sz)switch(ans[i]){
        case 1: puts("FILL(1)"); break;
        case 2: puts("FILL(2)"); break;
        case 3: puts("DROP(1)"); break;
        case 4: puts("DROP(2)"); break;
        case 5: puts("POUR(2,1)"); break;
        case 6: puts("POUR(1,2)");
      }
      return 0;
    }
    
    if(prev[0][b]<0)
      prev[0][b]=a*101+b, op[0][b]=3, q.push(b);
    if(prev[a][0]<0)
      prev[a][0]=a*101+b, op[a][0]=4, q.push(a*101);
    if(prev[A][b]<0)
      prev[A][b]=a*101+b, op[A][b]=1, q.push(A*101+b);
    if(prev[a][B]<0)
      prev[a][B]=a*101+b, op[a][B]=2, q.push(a*101+B);
    
    int na=a+b, nb=0;
    if(na>A)nb=na-A, na=A;
    if(prev[na][nb]<0)
      prev[na][nb]=a*101+b, op[na][nb]=5, q.push(na*101+nb);
    na=0, nb=a+b;
    if(nb>B)na=nb-B, nb=B;
    if(prev[na][nb]<0)
      prev[na][nb]=a*101+b, op[na][nb]=6, q.push(na*101+nb);
  }
  puts("impossible");
  
  return 0;
}