做了两道经典的BFS + 倒水问题

问题1


题目:
给两个杯子的装满水量分别为A,B,无限制接水,A,B无刻度,判断可否有一个杯子存留水为C,并记录最小次数的操作。
思路:
最少操作用BFS
有六种可以的方法"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"。
其中用队列存储结点,用栈存储操作顺序以便于最后逆序输出操作流程。
刚开始很不熟练,看了很多网上的答案才弄明白www。

代码在此

#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#define MaxSize 101
using namespace std;

struct node{
    int va,vb;
    int step;    //步数 
    int flag;    //哪一步操作 
    node* last;
};

int a,b,c,ans;
int visit[MaxSize][MaxSize] = {0};

queue<node> que;
stack<int> stk;

string str[6] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

void bfs(){
    node tmp;
    tmp.last = NULL;tmp.va = 0;tmp.vb = 0;tmp.step = 0;tmp.flag = 0;
    que.push(tmp);
    
    visit[0][0] = true;
    node t[400];
    int cnt = -1;
    
    while(!que.empty()){
        cnt++;
        t[cnt] = que.front();
        que.pop();
        for(int i = 1;i <= 6;i++){
            switch(i)
            {
                case 1:
                    tmp.va = a;
                    tmp.vb = t[cnt].vb;
                    tmp.flag = 1;
                    break;
                case 2:
                    tmp.va = t[cnt].va;
                    tmp.vb = b;
                    tmp.flag = 2;
                    break;
                case 3:
                    tmp.va = 0;
                    tmp.vb = t[cnt].vb;
                    tmp.flag = 3;
                    break;
                case 4:
                    tmp.va = t[cnt].va;
                    tmp.vb = 0;
                    tmp.flag = 4;
                    break;
                case 5:
                    if(t[cnt].va > b - t[cnt].vb){
                        tmp.va = t[cnt].va - (b-t[cnt].vb);
                        tmp.vb = b;
                    }
                    else{
                        tmp.va = 0;
                        tmp.vb = t[cnt].vb + t[cnt].va;
                    }
                    tmp.flag = 5;
                    break;
                case 6:
                    if(t[cnt].vb > a - t[cnt].va){
                        tmp.vb = t[cnt].vb - (a-t[cnt].va);
                        tmp.va = a;
                    }
                    else{
                        tmp.va = t[cnt].va + t[cnt].vb;
                        tmp.vb = 0;
                    }
                    tmp.flag = 6;
                    break;
            }
//            cout<<tmp.flag<<endl;
            if(visit[tmp.va][tmp.vb]) continue;
            
            visit[tmp.va][tmp.vb] = 1;
            tmp.step = t[cnt].step + 1;
//            cout<<tmp.step<<endl;
            tmp.last = &t[cnt];
            
            if(tmp.va == c || tmp.vb == c){
                ans = tmp.step;
                while(tmp.last != NULL){
                    stk.push(tmp.flag);
                    tmp = *tmp.last;
                }
                return;
            }
            que.push(tmp);
        }
    }
}

void print(){
    while(!stk.empty()){
//        cout<<"size = "<<stk.size()<<endl;
        int i = stk.top();
//        cout<<"i  = "<<i<<endl;
        cout<<str[i-1]<<endl;
        stk.pop();
    }
}

int main()
{
    cin>>a>>b>>c;
    bfs();
    if(ans == 0){
        cout<<"impossible"<<endl;
    }
    else{
        cout<<ans<<endl;
        print();
    }
    return 0;
}

问题2


大意:
给两个无刻度杯子,容积a,b,有c的可乐,问用这些可乐倒几次才能平分。
思路:
与上一题非常类似,特殊在有限制倒水
可行条件判断:有一杯为c/2且可乐c = 0
判断是否找过:visita的水量[c的剩余量](于上一题区别)
特别要注意:求每次操作后的剩余量时别错了。
上一道会了,这道题改一改就出来了~

代码在此

#include <iostream>
#include <string.h>
#include <queue>
#define MaxSize 103
using namespace std;

struct node{
    int va,vb;
    int step;    //步数 
    int flag;    //哪一步操作 
    int lastv;
    node* Last;
};

int a,b,c,ans;
int visit[MaxSize][MaxSize][MaxSize] = {0};


string str[6] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};


void bfs(){
    queue<node> que;
    node tmp;
    tmp.Last = NULL;tmp.va = 0;tmp.vb = 0;tmp.step = 0;tmp.flag = 0;tmp.lastv = c;
    que.push(tmp);
    
    visit[0][0][c] = true;
    node t[400];
    int cnt = -1;
    
    while(!que.empty()){
        cnt++;
        t[cnt] = que.front();
        que.pop();
        for(int i = 1;i <= 6;i++){
            switch(i)
            {
                case 1:
                    tmp.va = min(a,t[cnt].lastv);
                    tmp.vb = t[cnt].vb;
                    tmp.flag = 1;
                    tmp.lastv = t[cnt].lastv - (tmp.va - t[cnt].va);
                    break;
                case 2:
                    tmp.va = t[cnt].va;
                    tmp.vb = min(b,t[cnt].lastv);
                    tmp.flag = 2;
                    tmp.lastv = t[cnt].lastv - (tmp.vb - t[cnt].vb);
                    break;
                case 3:
                    tmp.va = 0;
                    tmp.vb = t[cnt].vb;
                    tmp.flag = 3;
                    tmp.lastv = t[cnt].lastv;
                    break;
                case 4:
                    tmp.va = t[cnt].va;
                    tmp.vb = 0;
                    tmp.flag = 4;
                    tmp.lastv = t[cnt].lastv;
                    break;
                case 5:
                    if(t[cnt].va > b - t[cnt].vb){
                        tmp.va = t[cnt].va - (b-t[cnt].vb);
                        tmp.vb = b;
                    }
                    else{
                        tmp.va = 0;
                        tmp.vb = t[cnt].vb + t[cnt].va;
                    }
                    tmp.flag = 5;
                    tmp.lastv = t[cnt].lastv;
                    break;
                case 6:
                    if(t[cnt].vb > a - t[cnt].va){
                        tmp.vb = t[cnt].vb - (a-t[cnt].va);
                        tmp.va = a;
                    }
                    else{
                        tmp.va = t[cnt].va + t[cnt].vb;
                        tmp.vb = 0;
                    }
                    tmp.flag = 6;
                    tmp.lastv = t[cnt].lastv;
                    break;
            }
            
            if(visit[tmp.va][tmp.vb][tmp.lastv]) continue;
            
            visit[tmp.va][tmp.vb][tmp.lastv] = 1;
            if(tmp.flag != 3 && tmp.flag != 4)tmp.step = t[cnt].step + 1;
            tmp.Last = &t[cnt];
            
            double k = c * 1.0 / 2;
            if((tmp.va == k || tmp.vb == k) && !tmp.lastv){
                ans = tmp.step;
                return;
            }
            que.push(tmp);
        }
    }
}

int main()
{
    while(cin>>c>>a>>b&& a && b && c){
        ans = 0;
        bfs();
        memset(visit,0,sizeof(visit));
        if(ans == 0){
            cout<<"NO"<<endl;
        }
        else cout<<ans<<endl;
    }
    return 0;
}

直接改上一道题的代码

#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#define MaxSize 101
using namespace std;

struct node{
    int va,vb;
    int step;    //步数 
    int flag;    //那一步操作 
    int lastv;
    node* Last;
};

int a,b,c,ans;
int visit[MaxSize][MaxSize][MaxSize] = {0};

queue<node> que;
stack<int> stk;

string str[6] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

void bfs(){
    node tmp;
    tmp.Last = NULL;tmp.va = 0;tmp.vb = 0;tmp.step = 0;tmp.flag = 0;tmp.lastv = c;
    que.push(tmp);
    
    visit[0][0][c] = true;
    node t[400];
    int cnt = -1;
    
    while(!que.empty()){
        cnt++;
        t[cnt] = que.front();
        que.pop();
        for(int i = 1;i <= 6;i++){
            switch(i)
            {
                case 1:
                    tmp.va = min(a,t[cnt].lastv);
                    tmp.vb = t[cnt].vb;
                    tmp.flag = 1;
                    tmp.lastv = t[cnt].lastv - (tmp.va - t[cnt].va);
                    cout<<"way = "<<tmp.flag<<" a = "<<tmp.va<<" b = "<<tmp.vb<<" last = "<<tmp.lastv<<endl;
                    break;
                case 2:
                    tmp.va = t[cnt].va;
                    tmp.vb = min(b,t[cnt].lastv);
                    tmp.flag = 2;
                    tmp.lastv = t[cnt].lastv - (tmp.vb - t[cnt].vb);
                    cout<<"way = "<<tmp.flag<<" a = "<<tmp.va<<" b = "<<tmp.vb<<" last = "<<tmp.lastv<<endl;
                    break;
                case 3:
                    tmp.va = 0;
                    tmp.vb = t[cnt].vb;
                    tmp.flag = 3;
                    tmp.lastv = t[cnt].lastv;
                    cout<<"way = "<<tmp.flag<<" a = "<<tmp.va<<" b = "<<tmp.vb<<" last = "<<tmp.lastv<<endl;
                    break;
                case 4:
                    tmp.va = t[cnt].va;
                    tmp.vb = 0;
                    tmp.flag = 4;
                    tmp.lastv = t[cnt].lastv;
                    cout<<"way = "<<tmp.flag<<" a = "<<tmp.va<<" b = "<<tmp.vb<<" last = "<<tmp.lastv<<endl;
                    break;
                case 5:
                    if(t[cnt].va > b - t[cnt].vb){
                        tmp.va = t[cnt].va - (b-t[cnt].vb);
                        tmp.vb = b;
                    }
                    else{
                        tmp.va = 0;
                        tmp.vb = t[cnt].vb + t[cnt].va;
                    }
                    tmp.flag = 5;
                    tmp.lastv = t[cnt].lastv;
                    cout<<"way = "<<tmp.flag<<" a = "<<tmp.va<<" b = "<<tmp.vb<<" last = "<<tmp.lastv<<endl;
                    break;
                case 6:
                    if(t[cnt].vb > a - t[cnt].va){
                        tmp.vb = t[cnt].vb - (a-t[cnt].va);
                        tmp.va = a;
                    }
                    else{
                        tmp.va = t[cnt].va + t[cnt].vb;
                        tmp.vb = 0;
                    }
                    tmp.flag = 6;
                    tmp.lastv = t[cnt].lastv;
                    cout<<"way = "<<tmp.flag<<" a = "<<tmp.va<<" b = "<<tmp.vb<<" last = "<<tmp.lastv<<endl;
                    break;
            }
            
            cout<<"size = "<<que.size()<<endl;
//            cout<<tmp.flag<<endl;
            if(visit[tmp.va][tmp.vb][tmp.lastv]) {
                cout<<"visited"<<endl;continue;
            }
            
            visit[tmp.va][tmp.vb][tmp.lastv] = 1;
            if(tmp.flag != 3 && tmp.flag != 4)tmp.step = t[cnt].step + 1;
//            cout<<tmp.step<<endl;
            tmp.Last = &t[cnt];
            
            double k = c * 1.0 / 2;
            if((tmp.va == k || tmp.vb == k) && !tmp.lastv){
                cout<<"--------------------------------------"<<endl;
                ans = tmp.step;
                while(tmp.Last != NULL){
                    stk.push(tmp.flag);
                    tmp = *tmp.Last;
                }
                return;
            }
            que.push(tmp);
        }
    }
}

void print(){
    while(!stk.empty()){
//        cout<<"size = "<<stk.size()<<endl;
        int i = stk.top();
//        cout<<"i  = "<<i<<endl;
        cout<<str[i-1]<<endl;
        stk.pop();
    }
}

int main()
{
    cin>>a>>b>>c;
    bfs();
    if(ans == 0){
        cout<<"impossible"<<endl;
    }
    else{
        cout<<ans<<endl;
        print();
    }
    return 0;
}


没啦~挺开心的,从早上看到倒水就头皮发麻,到能写明白了(o゚v゚)ノ真开心

Last modification:June 27th, 2020 at 10:24 pm
请赏我杯奶茶,让我快乐长肉