標準的廣度優先搜索，哈希判重。由於無法估計狀態數，需要用鏈隊列存儲搜索狀態。把初始狀態加入隊列，然後取出隊列中的首元素，對其狀態進行擴展。判斷不能有重複，否則是多餘的。如果當前擴展到的狀態三種錢幣的數目都大於等於目標狀態，則找到了解，輸出交易的次數。另外，爲防止重複按照某些規則交易使錢幣數目無意義地增長，人爲規定每種錢幣的數目不能超過目標狀態的若干倍（比如10倍即可）。

/* 
 * Problem: POI1997 ali
 * Author: Guo Jiabao
 * Time: 2008.11.28 20:42:00
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

struct coins
{
    int a,b,c,step;
};

class tQueue
{
    public:
        class tList
        {
            public:
                tList *next;
                coins v;
                tList(coins tv): v(tv)
                {
                    next=0;
                }
        };
        tList *first,*last;
        int Size;
        tQueue()
        {
            Size=0;
            first=last=0;
        }
        void ins(coins v)
        {
            if (first)
                last=last->next=new tList(v);
            else
                first=last=new tList(v);
            Size++;
        }
        coins pop()
        {
            Size--;
            tList *t=first;
            coins r=t->v;
            first=first->next;
            delete t;
            return r;
        }
        void reset()
        {
            tList *t;
            while (first)
            {
                t=first;
                first=first->next;
                delete t;
            }
            first=last=0;
        }
};

struct pri
{
    coins A,B;
};

const int LIM=100;

tQueue Q;
coins S,T;
pri P[11];
int N,M;
bool Hash[100][100][100];

void init()
{
    freopen("ali.in","r",stdin);
    freopen("ali.out","w",stdout);
    scanf("%d",&M);
}

void readfile()
{
    int i;
    scanf("%d%d%d%d%d%d",&S.a,&S.b,&S.c,&T.a,&T.b,&T.c);
    S.step=0;
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d%d%d%d%d%d",&P[i].A.a,&P[i].A.b,&P[i].A.c,&P[i].B.a,&P[i].B.b,&P[i].B.c);
    }
}

int solve()
{
    int k;
    coins i,j;
    if (S.a==T.a && S.b==T.b && S.c==T.c)
        return 0;
    Q.reset();
    memset(Hash,0,sizeof(Hash));
    Q.ins(S);
    Hash[S.a][S.b][S.c]=true;
    while (Q.Size)
    {
        i=Q.pop();
        j.step=i.step+1;
        for (k=1;k<=N;k++)
        {
            if (i.a >= P[k].A.a && i.b >= P[k].A.b && i.c >= P[k].A.c)
            {
                j.a=i.a-P[k].A.a+P[k].B.a;
                j.b=i.b-P[k].A.b+P[k].B.b;
                j.c=i.c-P[k].A.c+P[k].B.c;
                if (j.a>=T.a && j.b>=T.b && j.c>=T.c)
                    return j.step;
                if (j.a>=LIM || j.b>=LIM || j.c>=LIM) continue;
                if (!Hash[j.a][j.b][j.c])
                {
                    //printf("[%d,%d,%d] => [%d,%d,%d]n",i.a,i.b,i.c,j.a,j.b,j.c);
                    Hash[j.a][j.b][j.c]=true;
                    Q.ins(j);
                }
            }
        }
    }
    return -1;
}

int main()
{
    int i,Ans;
    init();
    for (i=1;i<=M;i++)
    {
        readfile();
        Ans=solve();
        if (Ans==-1)
            printf("NIEn");
        else
            printf("%dn",Ans);
    }
    return 0;
}

 阿里巴巴

想要“芝麻開門”，必須擁有一定數量的錢幣，其中包括至少z枚金幣，s枚銀幣和m枚銅幣。 最初，阿里巴巴擁有三種錢幣若干枚。他可以按照一定規則和芝麻之門的守護者進行交易。 每一種規則用以下形式表示：

z1, s1, m1 -> z2, s2, m2 (zi, si, mis屬於集合{0,1,2,3,4})。

這樣一種規則表示阿里巴巴可以將z1枚金幣, s1枚銀幣, m1枚銅幣換成z2枚金幣, s2枚銀幣, m2枚銅幣。一次交易而得的錢幣可以繼續參加下一次的交易。

任務

從文件中讀入幾組數據；對於每一組數據：

    * 阿里巴巴最初擁有的金銀銅三種錢幣數目
    * “芝麻開門”所需的金銀銅三種錢幣數目
    * 所有交易規則 

對每一組數據，判斷是否存在有限次的交易，使阿里巴巴能開啓芝麻之門。如果是，則將最少交易次數輸出，否則在輸出NIE(波蘭文NO)

把結果寫進文件中

輸入格式文件的第一行有一個整數d<=10,表示數據的組數。

接下來是d組數據，每組佔若干行。

第一行是三個數zp, sp, mp ，屬於集合{0,1,2,3,4}。表示阿里巴巴最初擁有的金銀銅數目。

第二行是三個數z, s, m ， 屬於集合{0,1,2,3,4}。表示芝麻開門所需的金銀銅數目。

第三行是規則總數r，1<=r<=10。

以下r行每行有六個數z1, s1, m1, z2, s2, m2 ，屬於集合{0,1,2,3,4}。表示一種簡單的交易z1, s1, m1 -> z2, s2, m2。

數字之間由若干個空格隔開。

輸出格式

文件的第i行爲第i組數據的答案：

一個非負整數——阿里巴巴要開啓芝麻之門所需的最少交易次數，或者

單詞NIE(波蘭文NO)

樣例輸入

2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2

樣例輸出

NIE
9