PKU : 3414 - Pots

問題概要

http://poj.org/problem?id=3414
容量A,Bまで入る2つのポットがあります.
最初の水の量は, 最初2つとも0です.
このとき, 次の操作を行いながら, どちらかのポットの容量をCにしてください.

• FILL(i) : iのポットを満タンにする
• DROP(i) : iのポットを空にする
• FILL(i,j) : iのポットからjのポットに水をうつす
  • iが空になるか, jが満タンになるまで, これを行う

アルゴリズム

BFSでできます.
状態は, 高々100*100なので, オーダは心配しなくて大丈夫です.

反省点

操作の情報はStateクラスの中にもたせるのではなく, 操作復元用の配列を作って行うべきだった.
しめじたんのブログがいい例.

プログラム

typedef pair<int,int> P;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

class State{
public:
  int a,b;
  vector<P> v;

  State(){}
  State(int _a,int _b,vector<P> _v){
    a = _a;
    b = _b;
    v = _v;
  }
};

int a,b,c;

void solve(){
  queue<State> open;
  bool closed[102][102];
  open.push(State(0,0,vector<P>()));
  memset(closed,0,sizeof(closed));

  vector<P> ans;

  while(!open.empty()){
    State st = open.front(); open.pop();
    if(closed[st.a][st.b]) continue;
    closed[st.a][st.b] = true;

    if(st.a == c || st.b == c){
      ans = st.v;
      break;
    }

    //FILL(1)
    int idx = st.v.size();
    st.v.push_back(P(0,1));
    open.push(State(a,st.b,st.v));

    //FILL(2)
    st.v[idx] = P(0,2);
    open.push(State(st.a,b,st.v));

    //DROP(1)
    st.v[idx] = P(0,-1);
    open.push(State(0,st.b,st.v));

    //DROP(2)
    st.v[idx] = P(0,-2);
    open.push(State(st.a,0,st.v));

    int A = st.a;
    int B = st.b;

    //POUR(1,2)
    st.v[idx] = P(1,2);
    open.push(State(max(0,A-(b-B)), min(b,B+A),st.v));

    //POUR(2,1)
    st.v[idx] = P(2,1);
    open.push(State(min(a,A+B), max(0,B-(a-A)),st.v));
  }

  if(ans.empty()){
    cout<<"impossible\n";
  }
  else{
    cout<<ans.size()<<endl;
    rep(i,ans.size()){
      if(ans[i].first > 0){
        printf("POUR(%d,%d)\n",ans[i].first,ans[i].second);
      }
      else if(ans[i].second > 0){
        printf("FILL(%d)\n",ans[i].second);
      }
      else{
        printf("DROP(%d)\n",-ans[i].second);
      }
    }
  }
}

int main(){
  cin>>a>>b>>c;
  solve();
}