记录编号	15973	评测结果	AAAAAA
题目名称	[POI 1997] 阿里巴巴	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	2.307 s
提交时间	2010-04-14 15:45:33	内存使用	121.00 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

using namespace std;

struct state
{
	int a,b,c;
}q[100000],chu,mo,qian[11],hou[11];
int step[100000];
int qt,qw=-1,n;
bool y[500][500][500];
void init()
{
	scanf("%d%d%d",&chu.a,&chu.b,&chu.c);
	scanf("%d%d%d",&mo.a,&mo.b,&mo.c);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d%d%d",&qian[i].a,&qian[i].b,&qian[i].c,&hou[i].a,&hou[i].b,&hou[i].c);
	}
}

bool make(state now,int stepnow)
{
	if (stepnow>200 || qw>=98000) return true;
	for (int i=1;i<=n;i++)
	{
		if (now.a>=qian[i].a && now.b>=qian[i].b && now.c>=qian[i].c)
		if (!y[now.a-qian[i].a+hou[i].a][now.b-qian[i].b+hou[i].b][now.c-qian[i].c+hou[i].c])
		if (now.a-qian[i].a+hou[i].a<=10 && now.b-qian[i].b+hou[i].b<=10 && now.c-qian[i].c+hou[i].c<=10)
		{
			y[now.a-qian[i].a+hou[i].a][now.b-qian[i].b+hou[i].b][now.c-qian[i].c+hou[i].c]=true;
			qw++;
			q[qw].a=now.a-qian[i].a+hou[i].a;
			q[qw].b=now.b-qian[i].b+hou[i].b;
			q[qw].c=now.c-qian[i].c+hou[i].c;
			step[qw]=stepnow+1;
			if (q[qw].a>=mo.a && q[qw].b>=mo.b && q[qw].c>=mo.c) return true;
		}
	}
	return false;
}

void solve()
{
	memset(y,0,sizeof(y));
	memset(step,0,sizeof(step));
	qt=0;qw=-1;
	q[++qw]=chu;
	y[chu.a][chu.b][chu.c]=true;
	while (qt<=qw)
	{
		if (make(q[qt],step[qt])) return;
		qt++;
	}
}

int main()
{
	freopen("ali.in","r",stdin);
	freopen("ali.out","w",stdout);
	int d;
	scanf("%d",&d);
	for (int i=1;i<=d;i++)
	{
		init();
		solve();
		if (q[qw].a>=mo.a && q[qw].b>=mo.b && q[qw].c>=mo.c) printf("%d\n",step[qw]);
		else printf("NIE\n");
	}
	return 0;
}