Beyond the Void
BYVoid
POI 1997 阿里巴巴 Ali Baba
本文正體字版由OpenCC轉換

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

相關日誌