程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HLJOJ1021(倒水問題)

HLJOJ1021(倒水問題)

編輯:C++入門知識

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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved