【广搜】倒水问题
2023-08-17 20:44:03
发布于：广东
1阅读
0回复
0点赞
传送门
似乎不能AC
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int n, m, need;
bool vis[108][108];
struct node {
int A, B, t;
string s;
};
queue<node> q;
void Push(node a) {
if(!vis[a.A][a.B]) {
q.push(a);
vis[a.A][a.B] = true;
}
}
void BFS() {
node cur = {0, 0, 0, ""};
q.push(cur);
vis[0][0] = true;
while(!q.empty()) {
node FF = q.front();
q.pop();
if(FF.A == need || FF.B == need) {
cout << FF.t << endl << FF.s;
return;
}
cur = {n, FF.B, FF.t + 1, FF.s + "FILL(1)\n"};
Push(cur);
cur = {FF.A, m, FF.t + 1, FF.s + "FILL(2)\n"};
Push(cur);
cur = {0, FF.B, FF.t + 1, FF.s + "DROP(1)\n"};
Push(cur);
cur = {FF.A, 0, FF.t + 1, FF.s + "DROP(2)\n"};
Push(cur);
int num = min(FF.A, m - FF.B);
cur = {FF.A - num, FF.B + num, FF.t + 1, FF.s + "POUR(1,2)\n"};
Push(cur);
num = min(FF.B, n - FF.A);
cur = {FF.A + num, FF.B - num, FF.t + 1, FF.s + "POUR(2,1)\n"};
Push(cur);
}
cout << "impossible";
}
int main(){
cin >> n >> m >> need;
BFS();
return 0;
}
有帮助，赞一个