罐子(kuangbin专题)

可以把两个罐子装水的状态看成一个二维的坐标, 然后这个坐标有六种方式改变(题中每个罐子的三种操作) 然后 BFS 来广搜每种状态即可

原题链接

题目描述

分析

可以把两个罐子装水的状态看成一个二维的坐标, 然后这个坐标有六种方式改变(题中每个罐子的三种操作) 然后 BFS 来广搜每种状态即可(这也是有技巧的,等会先贴上一个月前的代码)

一个月前的代码

把一个 BFS 的题硬生生的写成了枚举qwq

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1010;

int a,b,c;
bool st[N][N];

struct node{
    int a,b,cnt;
    int path[N];
};

string s[] = {	//  这是储存操作方法的数组 
     "FILL(1)"
    ,"FILL(2)"
    ,"DROP(1)"
    ,"DROP(2)"
    ,"POUR(1,2)"
    ,"POUR(2,1)"
};

//  输出路径 
void dy(node k)
{
    cout<<k.cnt<<endl;
    for(int i=0;i<k.cnt;i++)
    {
        cout<<s[k.path[i]]<<endl;
    }
    
}

void bfs()
{
    queue<node>q;
    node d;
    d.a = 0, d.b = 0, d.cnt = 0;
    memset(d.path,0,sizeof d.path);
    
    
    q.push(d);
    
    while(q.size())
    {
    	 
        auto t = q.front();
        q.pop();
        d = t;
        d.cnt++;
        
        //  ******* 这一堆的 if else !!!!! 
        if(t.a == c || t.b == c) 
        {
        	dy(t);
        	return ;
		}
        
        if(t.a != a)
        {
            d.a = a;
            d.b = t.b;
            if(!st[d.a][d.b])
            {
                st[d.a][d.b] = true;
                d.path[t.cnt] = 0;
                q.push(d);
            }
        }
        if(t.b != b)
        {
            d.b = b;
            d.a = t.a;
            if(!st[d.a][d.b])
            {
                st[d.a][d.b] = true;
                d.path[t.cnt] = 1;
                q.push(d);
            }
        }
        if(t.a)
        {
            d.a = 0;
            d.b = t.b;
            if(!st[d.a][d.b])
            {
                st[d.a][d.b] = true;
                d.path[t.cnt] = 2;
                q.push(d);
            }
        }
        if(t.b)
        {
            d.b = 0;
            d.a = t.a;
            if(!st[d.a][d.b])
            {
                st[d.a][d.b] = true;
                d.path[t.cnt] = 3;
                q.push(d);
            }
        }
        if(t.a && t.b<b)
        {
            if(t.a>b-t.b)
            {
                d.b = b;
                d.a = t.a - b + t.b;
                if(!st[d.a][d.b])
                {
                    st[d.a][d.b] = true;
                    d.path[t.cnt] = 4;
                    q.push(d);
                }
            }
            else 
            {
                d.a = 0;
                d.b = t.b + t.a;
                if(!st[d.a][d.b])
                {
                    st[d.a][d.b] = true;
                    d.path[t.cnt] = 4;
                    q.push(d);
                }
            }
        }
        if(t.b && t.a<a)
        {
            if(t.b>a-t.a)
            {
                d.a = a;
                d.b = t.b - a + t.a;
                if(!st[d.a][d.b])
                {
                    st[d.a][d.b] = true;
                    d.path[t.cnt] = 5;
                    q.push(d);
                }
            }
            else 
            {
                d.b = 0;
                d.a = t.a + t.b;
                if(!st[d.a][d.b])
                {
                    st[d.a][d.b] = true;
                    d.path[t.cnt] = 5;
                    q.push(d);
                }
            }
        }
    }
    cout<<"impossible"<<endl;
}

int main()
{
    cin>>a>>b>>c;
    
    bfs();
    
    return 0;
}

第二次代码

今天再次写这个题, 借鉴了地球OLBug 大佬的题解, 一个 for 循环就把我这 一大堆 if else 给代替了 还有一个是用 string s 来储存路径tql

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;

int a, b, c;
bool st[N][N], flag;    //  储存操作名称的数组
string str[] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};

struct node{    //  a, b,代表两个罐子里的水量, cnt 为此时的操作次数
    int a, b, cnt;
    string s;
};

void bfs()
{
	node d;
    queue<node>q;
    
    q.push({0, 0, 0, ""});
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        d = t;
        
        if(d.a == c || d.b == c)
        {
            cout << d.cnt << endl;
            
            // for(auto a:d.s)
            //     cout << str[a] << endl;
            
            for(int i = 0; i < d.s.size(); i ++)
                cout << str[d.s[i]] << endl;
            
            flag = true;
            break;
        }
        // 两个杯子之间相互倒水
        int t1 = min(t.a, b - t.b);
        int t2 = min(t.b, a - t.a);
        
        //  六个操作
        int g1[] = {a - t.a, 0, -t.a, 0, -t1, t2};
        int g2[] = {0, b - t.b, 0, -t.b, t1, -t2};
        
        for(int i = 0; i < 6; i ++)
        {
            
            d.a = t.a + g1[i];
            d.b = t.b + g2[i];
            
            if(!st[d.a][d.b])
            {
                char op = i;
                 string ss = d.s + op;
                
                //***** 如果要是这样的话, d.s里面就会多一个 0;
                //      我的理解是, d.s初始为 "" , ""对应的 ascii码为 0
                //      所以 d.s 的第一个字符一定为"" 即 对应的 ascii 值 0 
                //d.s += op;
                
                st[d.a][d.b] = true;
               
                q.push({d.a, d.b, d.cnt + 1, ss});
            }
            
        }
    }
    
    if(!flag) puts("impossible");
}

int main()
{
    cin >> a >> b >> c;
    
    bfs(); 
    
    return 0;
   
}