PKU 1606 Jugs (ZOJ 1005 Jugs)

http://poj.org/problem?id=1606
容量aのビン？と容量bのビンを使って容量nを創りだす時の手順を出力するというような問題。

幅優先探索。
時間制限はかなり緩い模様。
終了条件を適当にしていたため1OLEをくらった。

bool vis[1001][1001];

main(){
  int a,b,n;
  while(cin>>a>>b>>n){
    memset(vis,0,sizeof(vis));
    queue<pair<PI,deque<string> > > q;
    q.push(mp(mp(0,0),deque<string>()));
    while(!q.empty()){
      int ca=q.front().F.F,cb=q.front().F.S;
      deque<string> qq=q.front().S;q.pop();
      if(ca==n || cb==n){
        while(!qq.empty()){
          cout<<qq.front()<<endl;
          qq.pop_front();
        }
        cout<<"success"<<endl;
        break;
      }
      if(vis[ca][cb])continue;
      vis[ca][cb]=true;
      if(cb<b){
        qq.pb("fill B");
        q.push(mp(mp(ca,b),qq));
        qq.pop_back();
        if(ca){
          qq.pb("pour A B");
          int na=max(0,ca-(b-cb)),nb=min(ca+cb,b);
          q.push(mp(mp(na,nb),qq));
          qq.pop_back();
        }
      }
      if(ca<a){
        qq.pb("fill A");
        q.push(mp(mp(a,cb),qq));
        qq.pop_back();
        if(cb){
          qq.pb("pour B A");
          int nb=max(0,cb-(a-ca)),na=min(ca+cb,a);
          q.push(mp(mp(na,nb),qq));
          qq.pop_back();
        }        
      }
      if(ca){
        qq.pb("empty A");
        q.push(mp(mp(0,cb),qq));
        qq.pop_back();
      }
      if(cb){
        qq.pb("empty B");
        q.push(mp(mp(ca,0),qq));
        qq.pop_back();
      }
    }
  }
}

4/16追記
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5
と同じ問題のようです。