2
6 3 1
4 1 1
9 3 2
7 1 1

3
-1

典型的BFS(广度优先搜索）

每次倒水 有6种情况：

水杯A、B、C

A－>B

A -->C

B-->A

B-->C

C-->A

C-->B

按BFS思想构造 求目标的 深度即最少倒水次数

//
//  main.cpp
//  NYOJ-21 三个水杯
//  BFS  广度优先搜索
//  Created by [email protected] on 14-7－22.
//  Copyright (c) 2014年 Hzw. All rights reserved.
//


#include<iostream>
#include <queue>
#include <vector>
#include "string.h"
#include <algorithm>


using namespace std;
int cupCapacity[3],targetState[3];

class CupState
{
public:
    int iState[3];
    int iStep;
};


bool operator== ( const CupState  &data1, const CupState &data2)
{
    if( data1.iState[0]== data2.iState[0]
       && data1.iState[1] == data2.iState[1]
       && data1.iState[2] == data2.iState[2])
        return true;
    else
        return  false;
}

vector<CupState> visitBuf;

int pourWater(int sourceId,int targetId,CupState WaterState,queue<CupState> &qCupState)
{
    if(WaterState.iState[0] == targetState[0]
       && WaterState.iState[1] == targetState[1]
       && WaterState.iState[2] == targetState[2])
        return WaterState.iStep;
    
    if (sourceId == targetId ||
        WaterState.iState[sourceId] == 0
        || WaterState.iState[targetId] == cupCapacity[targetId]) {
        return -1;
    }
    if (cupCapacity[targetId] - WaterState.iState[targetId] >= WaterState.iState[sourceId]) {
        WaterState.iState[targetId] += WaterState.iState[sourceId];
        WaterState.iState[sourceId] = 0;
    }
    else
    {
        WaterState.iState[sourceId] -= (cupCapacity[targetId] - WaterState.iState[targetId]);
        WaterState.iState[targetId] = cupCapacity[targetId];
    }
    WaterState.iStep++;
    if(WaterState.iState[0] == targetState[0]
       && WaterState.iState[1] == targetState[1]
       && WaterState.iState[2] == targetState[2])
        return WaterState.iStep;
    if(find(visitBuf.begin(), visitBuf.end(), WaterState) ==visitBuf.end())
    {
        qCupState.push(WaterState);
        visitBuf.push_back(WaterState);
    }
    return -1;
}

int fBFS()
{
    CupState beginState, stateTemp;
    memset(&beginState, 0, sizeof(beginState));
    memset(&stateTemp, 0, sizeof(stateTemp));
    beginState.iState[0] = cupCapacity[0];
    queue<CupState> qCupState;
    qCupState.push(beginState);
    visitBuf.push_back(beginState);
    while (!qCupState.empty()) {
        CupState data = qCupState.front();
        qCupState.pop();
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
            {
                int iRet = pourWater(i, j, data,qCupState);
                if (iRet != -1) {
                    return iRet;
                }
            }
    }
    return -1;
};

int main()
{
    int M;
	cin>>M;
    while (M--) {
        visitBuf.clear();
        cin >> cupCapacity[0] >> cupCapacity[1] >> cupCapacity[2];
        cin >> targetState[0] >> targetState[1] >> targetState[2];
        cout << fBFS() << endl;
    }
    return 0;
}