首页 > 代码库 > poj3414-水杯
poj3414-水杯
题目链接 http://vjudge.net/problem/15208
解题思路
隐式图搜索,只有两个水杯状态表示也比较方便。
代码
#include<stdio.h>#include<string.h>#define MAX_SIZE 105#define QUE_SIZE 10005struct water { int a, b; int before; char step[20]; int now;};bool ZT[MAX_SIZE][MAX_SIZE];water Q[QUE_SIZE];int A, B, C;int search(int x, int y){ int front = -1, rear = -1; Q[++rear].a = x; Q[rear].b = y; ZT[x][y] = true; Q[rear].before = -1; Q[rear].now = 0; while(front != rear) { water u = Q[++front]; if(u.a == C || u.b == C) return front; if(!ZT[A][u.b]) { Q[++rear].a = A; Q[rear].b = u.b; strcpy(Q[rear].step, "FILL(1)"); Q[rear].now=u.now+1; Q[rear].before = front; ZT[A][u.b] = true; } if(!ZT[u.a][B]) { Q[++rear].a = u.a; Q[rear].b = B; strcpy(Q[rear].step, "FILL(2)"); Q[rear].now=u.now+1; Q[rear].before = front; ZT[A][u.b] = true; } if(!ZT[0][u.b]) { Q[++rear].a = 0; Q[rear].b = u.b; strcpy(Q[rear].step, "DROP(1)"); Q[rear].now=u.now+1; Q[rear].before = front; ZT[0][u.b] = true; } if(!ZT[u.a][0]) { Q[++rear].a = u.a; Q[rear].b = 0; strcpy(Q[rear].step, "DROP(2)"); Q[rear].now=u.now+1; Q[rear].before = front; ZT[u.a][0] = true; } int addW = A-u.a < u.b ? A-u.a : u.b; int leftW = A-u.a < u.b ? u.b-A+u.a : 0; if(!ZT[u.a+addW][leftW]) { Q[++rear].a = u.a+addW; Q[rear].b = leftW; strcpy(Q[rear].step, "POUR(2,1)"); Q[rear].now=u.now+1; Q[rear].before = front; ZT[u.a+addW][leftW] = true; } addW = B-u.b < u.a ? B-u.b : u.a; leftW = B-u.b < u.a ? u.a-B+u.b : 0; if(!ZT[leftW][u.b+addW]) { Q[++rear].a = leftW; Q[rear].b = u.b+addW; strcpy(Q[rear].step, "POUR(1,2)"); Q[rear].now=u.now+1; Q[rear].before = front; ZT[leftW][u.b+addW] = true; } } return -1;}void print(int nowStep){ if(nowStep == 0) return ; print(Q[nowStep].before); printf("%s\n", Q[nowStep].step);}int main(){ scanf("%d%d%d", &A, &B, &C); int Index = search(0,0); if(Index == -1) printf("impossible\n"); else { printf("%d\n", Q[Index].now); print(Index); } return 0;}
poj3414-水杯
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。