POJ 3414 Pots
好久没发关于ACM的文章了,以前的博客几个月没用了。今天随便水了一题,顺便发第一篇在这博客上的ACM的文章。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <algorithm> #include <set> #include <map> using namespace std; //fill 1 0 //drop 1 1 //fill 2 2 //drop 2 3 //pour(1, 2) 4 //pour(2, 1) 5 struct node { int v[2]; string step; int ans; }; int A, B, C; bool vis[110][110]; node bfs() { memset(vis, 0, sizeof(vis)); node cur, next; cur.v[0] = 0, cur.v[1] = 0, cur.step = "", cur.ans = 0; vis[0][0] = 1; queue<node> Q; Q.push(cur); while(!Q.empty()) { cur = Q.front(); Q.pop(); int a = cur.v[0], b = cur.v[1]; if(a == C || b == C) return cur; if(a != A && !vis[A][b]) //fill 1 { next = cur; next.v[0] = A; vis[A][b] = 1; next.step += '0', next.ans++; Q.push(next); } if(a > 0 && !vis[0][b]) //drop 1 { next = cur; next.v[0] = 0; vis[0][b] = 1; next.step += '1', next.ans++; Q.push(next); } if(b != B && !vis[a][B]) //fill 2 { next = cur; next.v[1] = B; vis[a][B] = 1; next.step += '2', next.ans++; Q.push(next); } if(b > 0 && !vis[a][0]) //drop 2 { next = cur; next.v[1] = 0; vis[a][0] = 1; next.step += '3', next.ans++; Q.push(next); } if(b != B && a+b < B && !vis[0][a+b]) //pour(1, 2) { next = cur; next.v[0] = 0, next.v[1] = a+b; vis[0][a+b] = 1; next.step += '4', next.ans++; Q.push(next); } if(b != B && a+b > B && !vis[a-B+b][B]) { next = cur; next.v[0] = a-B+b, next.v[1] = B; vis[a-B+b][B] = 1; next.step += '4', next.ans++; Q.push(next); } if(a != A && a+b < A && !vis[a+b][0]) //pour(2, 1) { next = cur; next.v[0] = a+b, next.v[1] = 0; vis[a+b][0] = 1; next.step += '5', next.ans++; Q.push(next); } if(a != A && a+b > A && !vis[A][b-A+a]) { next = cur; next.v[0] = A, next.v[1] = b-A+a; vis[A][b-A+a] = 1; next.step += '5', next.ans++; Q.push(next); } } node b; b.ans = -1; return b; } void print(node a) { int n = a.step.length(); printf("%d\n", a.ans); for(int i = 0; i < n; i++) { char c = a.step[i]; switch(c) { case '0': printf("FILL(1)\n"); break; case '1': printf("DROP(1)\n"); break; case '2': printf("FILL(2)\n"); break; case '3': printf("DROP(2)\n"); break; case '4': printf("POUR(1,2)\n"); break; case '5': printf("POUR(2,1)\n"); break; default: break; } } } int main() { while(~scanf("%d%d%d", &A, &B, &C)) { node ans = bfs(); if(ans.ans == -1) { printf("impossible\n"); continue ; } print(ans); } return 0; }