首页 > 代码库 > 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-水杯