比赛 |
2025暑期集训第7场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
倒水 |
最终得分 |
100 |
用户昵称 |
xpb |
运行时间 |
0.036 s |
代码语言 |
C++ |
内存使用 |
3.82 MiB |
提交时间 |
2025-08-11 16:26:49 |
显示代码纯文本
#include <bits/stdc++.h>>
using namespace std;
struct S {
int a, b, c, s;
};
int A, B, C, x;
int m = INT_MAX;
bool f = false;
bool t(int a, int b, int c) {
return a == x || b == x || c == x;
}
S p(int a, int b, int c, int f, int t, int s) {
S r;
r.s = s + 1;
if (f == 0) {
if (t == 1) {
int d = min(a, B - b);
r.a = a - d;
r.b = b + d;
r.c = c;
} else {
int d = min(a, C - c);
r.a = a - d;
r.b = b;
r.c = c + d;
}
} else if (f == 1) {
if (t == 0) {
int d = min(b, A - a);
r.a = a + d;
r.b = b - d;
r.c = c;
} else {
int d = min(b, C - c);
r.a = a;
r.b = b - d;
r.c = c + d;
}
} else {
if (t == 0) {
int d = min(c, A - a);
r.a = a + d;
r.b = b;
r.c = c - d;
} else {
int d = min(c, B - b);
r.a = a;
r.b = b + d;
r.c = c - d;
}
}
return r;
}
void dfs(int a, int b, int c, int s, vector<vector<vector<bool> > >& v) {
if (s >= m) return;
if (t(a, b, c)) {
if (s < m) {
m = s;
f = true;
}
return;
}
if (v[a][b][c]) return;
v[a][b][c] = true;
S s1 = p(a, b, c, 0, 1, s);
dfs(s1.a, s1.b, s1.c, s1.s, v);
S s2 = p(a, b, c, 0, 2, s);
dfs(s2.a, s2.b, s2.c, s2.s, v);
S s3 = p(a, b, c, 1, 0, s);
dfs(s3.a, s3.b, s3.c, s3.s, v);
S s4 = p(a, b, c, 1, 2, s);
dfs(s4.a, s4.b, s4.c, s4.s, v);
S s5 = p(a, b, c, 2, 0, s);
dfs(s5.a, s5.b, s5.c, s5.s, v);
S s6 = p(a, b, c, 2, 1, s);
dfs(s6.a, s6.b, s6.c, s6.s, v);
v[a][b][c] = false;
}
int main() {
freopen("pourwater.in", "r", stdin);
freopen("pourwater.out", "w", stdout);
cin >> A >> B >> C >> x;
if (A == x) {
cout << 0 << endl;
return 0;
}
vector<vector<vector<bool> > > v(A+1, vector<vector<bool> >(B+1, vector<bool>(C+1, false)));
dfs(A, 0, 0, 0, v);
if (f) cout << m << endl;
else cout << "false" << endl;
return 0;
}