AcWing 4222. 罐子
原题链接
简单
作者:
hnakedp
,
2024-04-26 16:00:40
,
所有人可见
,
阅读 1
dfs写的
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 110;
bool st[MAXN][MAXN];
int a, b, c;
int path[MAXN * MAXN], idx = 0;
int res[MAXN * MAXN];
int ans = 0x3f3f3f3f;
void print(int u) {
for (int i = 0; i < u; i++) {
if (res[i] == 0) cout << "FILL(1)" << endl;
if (res[i] == 1) cout << "FILL(2)" << endl;
if (res[i] == 2) cout << "DROP(1)" << endl;
if (res[i] == 3) cout << "DROP(2)" << endl;
if (res[i] == 4) cout << "POUR(1,2)" << endl;
if (res[i] == 5) cout << "POUR(2,1)" << endl;
}
}
// DFS搜索
void dfs(int aa, int bb) {
if (aa == c || bb == c) {
if (idx < ans) {
ans = idx;
memcpy(res, path, sizeof(int) * idx); // Fixed memcpy size
}
return;
}
if (st[aa][bb]) return;
st[aa][bb] = true;
// fill a
path[idx++] = 0;
dfs(a, bb);
idx--;
// fill b
path[idx++] = 1;
dfs(aa, b);
idx--;
// drop a
path[idx++] = 2;
dfs(0, bb);
idx--;
// drop b
path[idx++] = 3;
dfs(aa, 0);
idx--;
// pour a to b
path[idx++] = 4;
int pour = min(aa, b - bb);
dfs(aa - pour, bb + pour);
idx--;
// pour b to a
path[idx++] = 5;
pour = min(bb, a - aa);
dfs(aa + pour, bb - pour);
idx--;
st[aa][bb] = false;
}
int main() {
cin >> a >> b >> c;
dfs(0, 0);
if (ans == 0x3f3f3f3f) {
cout << "impossible" << endl;
} else {
cout << ans << endl;
print(ans);
}
return 0;
}