有4個(gè)瓶子，它們的容量分別是：

10升,6升, 5升, 4升

開(kāi)始的狀態(tài)是 [10,0,0,0]，也就是說(shuō)：第一個(gè)瓶子滿(mǎn)著，其它的都空著。
允許把酒從一個(gè)瓶子倒入另一個(gè)瓶子，但只能把一個(gè)瓶子倒?jié)M或把一個(gè)瓶子倒空，不能有中間狀態(tài)。這樣的一次倒酒動(dòng)作稱(chēng)為1次操作。
假設(shè)瓶子的容量和初始狀態(tài)不變，對(duì)于給定的目標(biāo)狀態(tài)，至少需要多少次操作才能實(shí)現(xiàn)？

輸入：最終狀態(tài) 輸出：最小操作次數(shù)（如無(wú)法實(shí)現(xiàn)，則輸出-1）

例如：
輸入：10 0 0 0
輸出：0
輸入：7 3 0 0
輸出：8

利用map完成窮搜

//10升, 6升, 5升,4升
#include <iostream>
#include <map>
#include <limits>
int capacity[] = { 10, 6, 5, 4 };
class state
{
public:
    state(int _b10, int _b6, int _b5, int _b4)
        :count(0), value(_b10 * 1000 + _b6 * 100 + _b5 * 10 + _b4)
    {
    }
    bool operator<(state rhs)const
    {
        return value < rhs.value;
    }
    int getvalue()const
    {
        return value;
    }
    short count;
protected:
    short value;
};
std::map<int,state> open, close;
void int2array(int content[], state s)
{
    int svalue = s.getvalue();
    content[0] = svalue / 1000;
    content[1] = svalue % 1000 / 100;
    content[2] = svalue % 100 / 10;
    content[3] = svalue % 10;
}
int array2int(int content[])
{
    return content[0] * 1000 + content[1] * 100
        + content[2] * 10 + content[3];
}
//一步轉(zhuǎn)移狀態(tài)
void derive(std::pair<int, state> sp)
{
    int c[4], t[4];
    int2array(c, sp.second);
    for (int i = 0; i < 4; ++i) // the bottle to pour from
    {
        if (c[i] == 0)
            continue; // no action on empty bottle
        for (int j = 0; j < 4; ++j) // the bottle to pour to
        {
            if (j == i || c[j] == capacity[j]) // don't pour to self or full bottle
                continue;
            //now we can derive a new state
            //state s=*this;
            //++s.count;
            int balance = capacity[j] - c[j];
            t[0] = c[0];
            t[1] = c[1];
            t[2] = c[2];
            t[3] = c[3];
            if (c[i] > balance) // source has more than target can hold
                t[i] -= balance, t[j] = capacity[j];
            else // target can hold everything currently in source
                t[j] += t[i], t[i] = 0;
            state si(t[0], t[1], t[2], t[3]);
            si.count = sp.second.count + 1;
            auto p = open.find(array2int(t));
            auto q = close.find(array2int(t));
            if (p != open.end()) // might encounter a better state
            {
                if (p->second.count > si.count)
                    p->second.count = si.count;
            }
            else if (q == close.end())
            {
                open.insert(std::pair<int, state>(array2int(t),si));
            }
        }
    }
}
int main() {
    int n = 4;
    int input;
    int min = INT_MAX;
    int initvalue = 1;
    //輸入初始狀態(tài)
    open.insert(std::pair<int, state>(10000, state(10, 0, 0, 0)));
    //輸入的四個(gè)數(shù)變?yōu)橐粋€(gè)數(shù)
    for (int i = 0; i < n; i++)
    {
        std::cin >> input;
        if (i == 0)
            initvalue = input;
        else
            initvalue = initvalue * 10 + input;
    }
    //窮搜整個(gè)空間,取出open狀態(tài)加入close，新?tīng)顟B(tài)加入open
    while (!open.empty())
    {
        auto p = open.begin();
        auto s = *p;
        close.insert(s);
        open.erase(p);
        derive(s);
    }
    //printf 
    for (auto i = close.begin(); i != close.end(); ++i)
    {
        std::cout << i->first << " " << i->second.count << std::endl;
    }
    auto i = close.find(initvalue);
    if(i != close.end())
        if (min > i->second.count)
            min = i->second.count;
    if (min == INT_MAX)
        std::cout << -1 << std::endl;
    std::cout << min << std::endl;
    return 0;
}