Beyond the Void
BYVoid
POI 1997 阿里巴巴 Ali Baba

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

上次修改时间 2017-02-03

相关日志