2816119_ac_15ms_4072k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int a, b, c;
struct node
{
	int a, b;
	char op[10];
};

int mark[1001][1001];
int pre[10001];
node que[10001];
int f, r;

void output()
{
	int n, i;
	int out[10001];

	n = 0;
	while(r!=-1)
	{
		out[n++] = r;
		r = pre[r];
	}
	for(i = n - 2; i >= 0; i--)
		puts(que[out[i]].op);
	puts("success");
}

void bfs()
{
	node t, p;

	while(f!=r)
	{
		++f;
		t = que[f];
		p = t;
		if(p.a)//empty A
		{
			p.a = 0;
			if(mark[p.a][p.b]==0)
			{
				mark[p.a][p.b] = 1;
				strcpy(p.op,"empty A");
				que[++r] = p;
				pre[r] = f;
			}
		}
		p = t;
		if(p.b)//empty B
		{
			p.b = 0;
			if(mark[p.a][p.b]==0)
			{
				mark[p.a][p.b] = 1;
				strcpy(p.op,"empty B");
				que[++r] = p;
				pre[r] = f;
			}
		}
		p = t;
		if(p.a!=a)//fill A
		{
			p.a = a;
			if(mark[p.a][p.b]==0)
			{
				mark[p.a][p.b] = 1;
				strcpy(p.op,"fill A");
				que[++r] = p;
				pre[r] = f;
				if(p.a==c||p.b==c)
				{
					output();
					return ;
				}
			}
		}
		p = t;
		if(p.b!=b)//fill B
		{
			p.b = b;
			if(mark[p.a][p.b]==0)
			{
				mark[p.a][p.b] = 1;
				strcpy(p.op,"fill B");
				que[++r] = p;
				pre[r] = f;
				if(p.a==c||p.b==c)
				{
					output();
					return ;
				}
			}
		}
		p = t;
		if(p.b!=b&&p.a)//pour A B
		{
			int tt;

			tt = b - p.b;
			if(tt > p.a)
				tt = p.a;
			p.a -= tt;
			p.b += tt;
			if(mark[p.a][p.b]==0)
			{
				mark[p.a][p.b] = 1;
				strcpy(p.op,"pour A B");
				que[++r] = p;
				pre[r] = f;
				if(p.a==c||p.b==c)
				{
					output();
					return ;
				}
			}
		}
		p = t;
		if(p.a!=a&&p.b)//pour B A
		{
			int tt;

			tt = a - p.a;
			if(tt > p.b)
				tt = p.b;
			p.b -= tt;
			p.a += tt;
			if(mark[p.a][p.b]==0)
			{
				mark[p.a][p.b] = 1;
				strcpy(p.op,"pour B A");
				que[++r] = p;
				pre[r] = f;
				if(p.a==c||p.b==c)
				{
					output();
					return ;
				}
			}
		}
	}
	puts("Y");
}

int main()
{
	node t;

	while(scanf("%d%d%d",&a,&b,&c)==3)
	{
		t.a = 0;
		t.b = 0;
		f = r = -1;
		que[++r] = t;
		pre[0] = -1;
		memset(mark,0,sizeof(mark));
		mark[0][0] = 1;
		bfs();
	}
	return 0;
}