| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
擦。忘记输出次数一直wa!1、单组数据
2、可能多种答案,随便输出一种就行
3、别忘了impossible,还有次数。
第一次在PKU贴代码
#include <cstdio>
#include <iostream>
#include <cstddef>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 110;
struct Statue {
int cnt, a[2];
string op; // 0x: FILL(x); 1x: DROP(x); 2xy: POUR(x, y)
}que[maxn * maxn];
int A[2], C, front, tail;
int mark[maxn][maxn];
void drop(const Statue& nn, int id) {
Statue node = nn;
node.a[id] = 0;
if (!mark[node.a[0]][node.a[1]]) {
mark[node.a[0]][node.a[1]] = 1;
node.op += "1";
node.op += ('0' + (id + 1));
++node.cnt;
que[front++] = node;
}
}
void fill(const Statue& nn, int id) {
Statue node = nn;
node.a[id] = A[id];
if (!mark[node.a[0]][node.a[1]]) {
mark[node.a[0]][node.a[1]] = 1;
node.op += "0";
node.op += ('0' + (id + 1));
++node.cnt;
que[front++] = node;
}
}
void pour(const Statue& nn, int f, int t) {
Statue node = nn;
int sum = (node.a[f] + node.a[t]);
if (sum > A[t]) {
node.a[t] = A[t];
node.a[f] = sum - A[t];
} else {
node.a[f] = 0;
node.a[t] = sum;
}
if (!mark[node.a[0]][node.a[1]]) {
mark[node.a[0]][node.a[1]] = 1;
++node.cnt;
node.op += "2";
node.op += ('0' + (f + 1));
node.op += ('0' + (t + 1));
que[front++] = node;
}
}
bool bfs() {
while (tail < front) {
Statue node = que[tail++];
if (node.a[0] == C || node.a[1] == C) {
printf("%d\n", node.cnt);
size_t sz = node.op.size();
for (size_t i = 0; i != sz; ++i) {
if (node.op[i] == '0') {
cout << "FILL(" << node.op[++i] << ")" << endl;
} else if (node.op[i] == '1') {
cout << "DROP(" << node.op[++i] << ")" << endl;
} else {
cout << "POUR(" << node.op[++i] << ",";
cout << node.op[++i] << ")" << endl;
}
}
return true;
}
if (node.a[0]) {
drop(node, 0);
if (node.a[1] < A[1]) pour(node, 0, 1);
}
if (node.a[0] < A[0]) fill(node, 0);
if (node.a[1]) {
drop(node, 1);
if (node.a[0] < A[0]) pour(node, 1, 0);
}
if (node.a[1] < A[1]) fill(node, 1);
}
return 0;
}
int main() {
scanf ("%d%d%d", &A[0], &A[1], &C);
if (C == 0) {
puts("0");
return 0;
}
if (A[0] == C) {
puts("1\nFILL(1)");
} else if (A[1] == C) {
puts("1\nFILL(2)");
} else {
Statue node;
front = tail = 0;
node.a[0] = 0, node.a[1] = 0;
node.cnt = 0, node.op = "";
que[front++] = node;
memset(mark, 0, sizeof (mark));
mark[0][0] = 1;
if (!bfs()) puts("impossible");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator