如何制作或购买一个适合装罐头的kuangbin专题罐子？

本文共计1088个文字，预计阅读时间需要5分钟。

可以将两个装水的状态看作一个二维的坐标，然后通过六种方式变换这个坐标（每个坐标的每个元素有三种操作），接着使用BFS来广搜所有可能的状态，实现题目要求。

可以把两个罐子装水的状态看成一个二维的坐标, 然后这个坐标有六种方式改变(题中每个罐子的三种操作) 然后 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; }