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