HLJOJ1021(倒水問題)

HLJOJ1021(倒水問題)

描述:設大，中，小三個杯子的容量分別為a，b，c。開始時，A中裝滿了水，B，C都為空。你的任務是，判斷經過一系列操作後，能否使其中一個杯子裡出現x升水。（一次操作指把x杯子裡的水倒入y杯子中，因為杯子沒有刻度 ，所以倒水時只允許將x杯子倒空，或將y杯子倒滿。

輸入：四個整數a,b,c,x.(1<=a<=b<=c<100,0

輸出：能的話，輸出最短的操作步數，否則輸出Impossible.

樣例:

6 3 1 4

10 8 7 5

輸出:

3

impssbile

第一個樣例所經過的步驟：(6,0,0)->(3,3,0)->(3,2,1)->(4,2,0)

只有六種狀態，BFS一下

a->b,a->c

b->a,b->c

c->a,c->b

#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
const double eps = 1e-6;
const int MAXN = 100010;
const double INF = 1e20;
int visit[101][101];
int aa[3];
int x;
struct Node
{
    int cap[3],step;
    Node(int x, int y,int z,int p)
    {
        cap[0] = x,cap[1] = y, cap[2] = z , step = p;
    }
    Node() {}
};
 
int BFS()
{
    memset(visit,0,sizeof(visit));
    queue Q;
    Q.push(Node(aa[0],0,0,0));
    visit[aa[0]][0] = 1;
    while(!Q.empty())
    {
        Node temp = Q.front(),temp2;
        Q.pop();
       if(temp.cap[0] == x || temp.cap[1] == x || temp.cap[2] == x) return temp.step;
 
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(i == j) continue;
                int cha = aa[j] - temp.cap[j];
                temp2 = temp;
 
                if(temp2.cap[i] && cha )
                {
 
                    if(temp2.cap[i] > cha)
                    {
                        temp2.cap[j] = aa[j];
                        temp2.cap[i] -= cha;
                    }
                    else
                    {
                        temp2.cap[j] += temp2.cap[i];
                        temp2.cap[i] = 0;
 
                    }
 
                    if(!visit[temp2.cap[0]][temp2.cap[1]])
                    {
                        visit[temp2.cap[0]][temp2.cap[1]] = 1;
                        Q.push(Node(temp2.cap[0],temp2.cap[1],temp2.cap[2],temp2.step+1));
                    }
                }
 
            }
        }
    }
 
    return -1;
}
 
int main()
{
    #ifdef xxz
    freopen("in.txt","r",stdin);
    #endif // xxz
    while(~scanf("%d%d%d%d", &aa[0], &aa[1], &aa[2],&x))
    {
        int ans = BFS();
        if(ans == -1) printf("Impossible\n");
        else printf("%d\n",ans);
    }
    return 0;
}