[kuangbin带你飞]专题一 简单搜索 H

题目：[kuangbin带你飞]专题一 简单搜索 H

题目关键在保存路径，我用了栈来保存，看了大神的代码，用的是数组保存，这样空间占的比较小，然后直接循环6种操作方法，更简洁一些。我变成3中操作，在细分两种，复杂了。

我的代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
bool vis[110][110];
int A,B,C;
struct node{
    int apot;
    int bpot;
    int step;
    queue<string> path;
};

node fill(node nownode,int s){
    node nextnode = nownode;
    if(s){//a装满 
        nextnode.apot = A;
        nextnode.path.push("FILL(1)");
    }else{
        nextnode.bpot = B;
        nextnode.path.push("FILL(2)");
        
    }
//   cout<<"nextnode on fill : "<<nextnode.apot<<" "<<nextnode.bpot<<" step "<< nextnode.step<<endl;
    return nextnode;
}

node drop(node nownode,int s){
    node nextnode = nownode;
    if(s){//a倒掉 
        nextnode.apot = 0;
        nextnode.path.push("DROP(1)");
    }else{
        nextnode.bpot = 0;
        nextnode.path.push("DROP(2)");
    }
//  cout<<"nextnode on drop : "<<nextnode.apot<<" "<<nextnode.bpot<<" step "<< nextnode.step<<endl;
    return nextnode;
}

node pour(node nownode,int s){
    node nextnode;
    nextnode = nownode;
    if(s){
        //a倒b
         nextnode.apot = (nownode.apot+nownode.bpot) - B;
         if(nextnode.apot<0) nextnode.apot = 0;
         nextnode.bpot = nownode.apot + nownode.bpot;
         if(nextnode.bpot>B) nextnode.bpot = B;
         nextnode.path.push("POUR(1,2)");
    }else{
        nextnode.bpot = (nownode.apot+nownode.bpot) -A;
        if(nextnode.bpot<0) nextnode.bpot = 0;
        nextnode.apot = nownode.apot + nownode.bpot;
        if(nextnode.apot>A) nextnode.apot = A;
        nextnode.path.push("POUR(2,1)");
    }
//  cout<<"nextnode on pour : "<<nextnode.apot<<" "<<nextnode.bpot<<" step "<< nextnode.step<<endl;
    return nextnode;
}

node func(node nownode,int i,int s){
    
    if(i==0)
        return fill(nownode,s);
    if(i==1)
        return drop(nownode,s);
    if(i==2)
        return pour(nownode,s);

}

node bfs(node start){
    queue<node> Q;
    Q.push(start);
    vis[start.apot][start.bpot] = true;
    while(!Q.empty()){
        node nownode;
        node nextnode;
        nownode = Q.front();Q.pop();
        if(nownode.step!=0)
//      cout<<"nownode "<<nownode.apot<<" "<<nownode.bpot<<" "<<nownode.path.back()<<endl;

        if(nownode.apot==C || nownode.bpot ==C){
            return nownode;
        }
        for(int i=0;i<3;i++){
            for(int s=0;s<=1;s++){
                nextnode=func(nownode,i,s); 
                if(!vis[nextnode.apot][nextnode.bpot]){
//                  cout<<"next "<<nextnode.apot<<" "<<nextnode.bpot<<" "<<nextnode.path.back()<<endl;
                    vis[nextnode.apot][nextnode.bpot] = true;
                    nextnode.step = nownode.step+1;
                    Q.push(nextnode);
                }   
            }
        }
        
        
        
    }
    node errnode;
    errnode.apot = -1;
    return errnode; 
}
int main(){
    cin>>A>>B>>C;
    node start;
    start.apot = 0;
    start.bpot = 0;
    start.step = 0;
    node ansnode = bfs(start);
    if(ansnode.apot == -1){
        cout<<"impossible"<<endl;
    }else{
        cout<<ansnode.step<<endl;
        while(!ansnode.path.empty()){
            cout<<ansnode.path.front()<<endl;
            ansnode.path.pop();
        }
    }
    return 0;
}