2250729_ac_0ms_44k.cc

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

# include <stdio.h>

int pos[9][2];
int pz[3][3];
char tmp[10][2];

void up()
{
	printf("u");
	pos[0][0]--;
	pz[pos[0][0]+1][pos[0][1]] = pz[pos[0][0]][pos[0][1]];
	pz[pos[0][0]][pos[0][1]] = 0;
	pos[pz[pos[0][0]+1][pos[0][1]]][0]++;
}

void down()
{
	printf("d");
	pos[0][0]++;
	pz[pos[0][0]-1][pos[0][1]] = pz[pos[0][0]][pos[0][1]];
	pz[pos[0][0]][pos[0][1]] = 0;
	pos[pz[pos[0][0]-1][pos[0][1]]][0]--;
}

void left()
{
	printf("l");
	pos[0][1]--;
	pz[pos[0][0]][pos[0][1]+1] = pz[pos[0][0]][pos[0][1]];
	pz[pos[0][0]][pos[0][1]] = 0;
	pos[pz[pos[0][0]][pos[0][1]+1]][1]++;
}

void right()
{
	printf("r");
	pos[0][1]++;
	pz[pos[0][0]][pos[0][1]-1] = pz[pos[0][0]][pos[0][1]];
	pz[pos[0][0]][pos[0][1]] = 0;
	pos[pz[pos[0][0]][pos[0][1]-1]][1]--;
}

void done()
{
	if(pos[0][0]==2)
		up();
	if(pos[0][1]==0)
		right();
	right(),down(),left(),up(),left(),down(),right(),right(),up(),left(),down(),right(),up(),left(),left(),down(),right();
}

void finish()
{
	int num = 0;

	if(pos[0][0]==1)
		down();
	if(pos[0][1]==1)
		right();
	if(pz[1][2]<pz[1][1])
		num++;
	if(pz[2][1]<pz[1][1])
		num++;
	if(pz[2][1]<pz[1][2])
		num++;
	while(pz[1][1]!=5||pz[1][2]!=6||pz[2][1]!=8||pz[2][2]!=0)
		up(),left(),down(),right();
}

void solve()
{
	if(pz[0][0]!=1)
	{
		if(pos[1][0]!=0)
		{
			again:;
			while(pos[0][0]!=pos[1][0]-1)
			{
				if(pos[0][0]>=pos[1][0])
					up();
				else
					down();
			}
			while(pos[0][1]!=pos[1][1])
			{
				if(pos[0][1]>pos[1][1])
					left();
				else
					right();
			}
			down();
			if(pos[1][0]!=0)
			{
				if(pos[0][1]==0)
					right();
				else
					left();
				goto again;
			}
		}
		if(pos[0][0]==0)
			down();
		if(pos[0][0]==2)
			up();
		while(pos[0][1]<pos[1][1])
			right();
		while(pos[0][1]>pos[1][1])
			left();
		while(pz[0][0]!=1)
			left(),up(),right(),down(),left();
	}
	if(pz[0][1]!=2)
	{
		if(pos[2][1]==0)
		{
			if(pos[0][1]==0)
				right();
			else
				if(pos[0][1]==2)
					left();
			while(pos[0][0]!=pos[2][0])
				if(pos[0][0]<pos[2][0])
					down();
				else
					up();
			m1:;
			left();
			if(pos[0][0]==2)
				up(),right(),down(),right(),up(),up(),left(),down();
			else
				down(),right(),right(),up(),up(),left(),down();
		}
		else
			if(pos[2][1]==1)
			{
				if(pos[0][1]==0)
					right();
				if(pos[2][1]==1)
				{
					if(pos[0][0]<pos[2][0])
						down(),right(),up(),up(),left(),down();
					else
						right(),up(),up(),left(),down();
				}
				else
					goto m1;
			}
			else
			{
				if(pos[0][1]==2)
					left();
				else
					if(pos[0][1]==0)
						right();
				while(pos[0][0]!=pos[2][0])
					if(pos[0][0]<pos[2][0])
						down();
					else
						up();
				right();
				while(pz[0][1]!=2)
					up(),left(),down(),right(),up();
			}
	}
	if(pz[0][2]==0)
		down();
	if(pz[0][2]!=3)
	{
		if(pos[3][1]==0)
		{
			if(pos[0][1]==0)
				right();
			else
				if(pos[0][1]==2)
					left();
			if(pos[0][0]>pos[3][0])
				up();
			else
				if(pos[0][0]<pos[3][0])
					down();
			left();
			if(pz[1][1]==3)
				up(),right(),down(),right(),up(),left(),left(),down();
			else
				up(),right(),down(),left(),up(),up(),right(),down(),right(),up(),left(),left(),down();
		}
		else
			if(pos[3][1]==2)
			{
				if(pos[0][1]==0)
					right();
				else
					if(pos[0][1]==2)
						left();
				if(pos[0][0]>pos[3][0])
					up();
				else
					if(pos[0][0]<pos[3][0])
						down();
				right();
				if(pz[1][1]==3)
					down(),left(),left(),up(),up(),right(),down(),right(),up(),left(),left(),down();
				else
					up(),left(),down(),left(),up(),up(),right(),down(),right(),up(),left(),left(),down();
			}
			else
			{
				if(pz[1][1]==3)
				{
					if(pz[1][2]==0)
						down();
					if(pos[0][0]==2)
					{
						while(pos[0][1]!=0)
							left();
						up();
					}
					up(),right(),down(),right(),up(),left(),left(),down();
				}
				else
				{
					if(pos[0][0]==2)
						up();
					if(pos[0][1]==0)
						right();
					if(pos[0][1]==2)
						left();
					down(),left(),up(),up(),right(),down(),right(),up(),left(),left(),down();
				}
			}
	}
	if(pz[1][0]!=4||pz[2][0]!=7)
	{
		if(pz[2][2]!=7)
		{
			if(pz[2][0]==7)
			{
				if(pos[0][1]==0)
					right();
				if(pos[0][1]==2)
					left();
				if(pos[0][0]==1)
					down();
				left(),up(),right(),right(),down(),left();
			}
			else
				if(pz[1][0]==7)
				{
					if(pos[0][1]==0)
						right();
					if(pos[0][0]==2)
						up();
					if(pos[0][1]==2)
						left();
					left(),down(),right(),up(),right(),down(),left();
				}
				else
					if(pz[1][1]==7)
					{
						if(pos[0][0]==1)
							down();
						if(pos[0][1]==0)
							right();
						if(pos[0][1]==2)
							left();
						up(),right(),down(),left();
					}
					else
						if(pz[2][1]==7)
						{
							if(pos[0][0]==2)
								up();
							if(pos[0][1]==0)
								right();
							if(pos[0][1]==2)
								left();
							right(),down(),left();
						}
						else
							if(pz[1][2]==7)
							{
								if(pos[0][0]==1)
									down();
								while(pos[0][1]!=2)
									right();
								up();
							}
		}
		if(pz[1][2]==0)
			left();
		if(pz[1][2]==4)
			done();
		else
		{
			if(pz[1][0]==4)
			{
				if(pos[0][0]==1)
					down();
				if(pos[0][1]==1)
					left();
				up(),right(),down(),left();
			}
			else
				if(pz[2][0]==4)
				{
					if(pos[0][1]==0)
						right();
					if(pos[0][0]==1)
						down();
					left();
				}
				else
					if(pz[1][1]==4)
					{
						if(pos[0][0]==1)
							down();
						if(pos[0][1]==0)
							right();
						up();
					}
			if(pos[0][0]==1)
			{
				while(pos[0][1]!=0)
					left();
				down();
			}
			right(),right(),up(),left(),left(),down(),right();
		}
		finish();
	}
}

int check()
{
	int i, j;
	int num;

	num = 0;
	for(i = 0; i < 9; i++)
		if(tmp[i][0]!='x')
		{
			for(j = i+1; j < 9; j++)
				if(tmp[j][0]!='x'&&tmp[j][0]<tmp[i][0])
					num++;
		}
	return num%2;
}

void input()
{
	int i, j;
	
	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
		{
			scanf("%s",tmp[i*3+j]);
			if(tmp[i*3+j][0]=='x')
				pz[i][j] = 0, pos[0][0] = i, pos[0][1] = j;
			else
				pz[i][j] = tmp[i*3+j][0] - '0', pos[pz[i][j]][0] = i, pos[pz[i][j]][1] = j;
		}
	if(check())
		printf("unsolvable\n");
	else
		solve();
}

int main()
{
	input();
	return 1;
}