This post is written in Chinese. Please consider using Google Translate

标准的广度优先搜索，哈希判重。由于无法估计状态数，需要用链队列存储搜索状态。把初始状态加入队列，然后取出队列中的首元素，对其状态进行扩展。判断不能有重复，否则是多余的。如果当前扩展到的状态三种钱币的数目都大于等于目标状态，则找到了解，输出交易的次数。另外，为防止重复按照某些规则交易使钱币数目无意义地增长，人为规定每种钱币的数目不能超过目标状态的若干倍（比如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