2254363_ac_0ms_32k.c

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

# include <stdio.h>
# include <stdlib.h>

FILE *aa = stdout, *bb = stdin;
int n, l = 0;
int pz[11][11];
int pos[101][2];
int p, tmp[102];
char com[1000];

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

	num = 0;
	for(i = 0; i < p; i++)
		if(tmp[i])
			for(j = i+1; j < p; j++)
				if(tmp[j]&&tmp[j]<tmp[i])
					num++;
	return num%2;
}

void Right()
{
	pos[0][1]++;
	com[l++] = 'R';
	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 Down()
{
	pos[0][0]++;
	com[l++] = 'D';
	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 up()
{
	fprintf(aa,"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()
{
	fprintf(aa,"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()
{
	fprintf(aa,"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()
{
	fprintf(aa,"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 push(int w, int h, int b)
{
	int num;

	num = w*n+h+1;
	if(pos[num][0]!=w)
	{
		if(pos[0][0]!=n-1)
			down();
		if(pz[w][h]==num)
			return ;
		if(pos[num][1]==pos[0][1])
		{
			if(pos[0][1]==0)
				right();
			else
				left();
		}
		while(pos[num][0]!=pos[0][0])
			if(pos[num][0]>pos[0][0])
				down();
			else
				up();
		while(pos[num][1]!=pos[0][1]-1)
			if(pos[num][1]<pos[0][1]-1)
				left();
			else
				right();
		left();
		while(pos[num][1]<n-1)
			if(pos[0][0]==n-1)
				up(),right(),right(),down(),left();
			else
				down(),right(),right(),up(),left();
		while(pos[num][0]>w+b)
			up(),right(),down(),left(),up();
	}
	if(!b)
	{
		if(pos[0][0]==w)
			down();
		while(pos[0][1]!=pos[num][1])
			if(pos[0][1]>pos[num][1])
				left();
			else
				right();
		while(pos[0][0]>w+1)
			up();
		while(pos[num][1]!=h)
			left(),up(),right(),down(),left();
	}
	else
	{
		right(),down(),left(),left(),up();
		while(pos[0][1]>0)
			left();
		up();
		while(pos[0][1]<pos[num][1])
			right();
		down(),right(),up();
		while(pos[0][1]>0)
			left();
		down();
	}
}

void finish()
{
	if(pos[0][0]==n-2)
		down();
	if(pos[0][1]==n-2)
		right();
	while(pz[n-2][n-2]!=n*n-n-1||pz[n-2][n-1]!=n*n-n||pz[n-1][n-2]!=n*n-1)
		left(),up(),right(),down();
}

void Push(int m)
{
	int num1, num2;

	num1 = n*n-n+1+m;
	num2 = n*n-2*n+1+m;

	if(pz[n-1][n-1]!=num1)
	{
		if(pos[0][0]==n-2)
			down();
		while(pos[0][1]!=pos[num1][1]+(pos[0][0]==pos[num1][0]))
			if(pos[0][1]<pos[num1][1]+(pos[0][0]==pos[num1][0]))
				right();
			else
				left();
		if(pos[0][0]!=pos[num1][0])
			up();
		else
			up(),left();
		while(pz[n-1][n-1]!=num1)
			right(),down(),left(),up(),right();
	}
	if(pos[0][1]==n-1)
		left();
	if(pz[n-2][n-1]==num2)
	{
		if(pos[0][0]==n-1)
			up();
		while(pos[0][1]<n-2)
			right();
		right(),down(),left(),left(),up(),right(),down(),right(),up(),left(),left(),down(),right(),up();
	}
	else
	{
		if(pos[0][0]==n-2)
			down();
		while(pos[0][1]!=pos[num2][1]+(pos[0][0]==pos[num2][0]))
			if(pos[0][1]<pos[num2][1]+(pos[0][0]==pos[num2][0]))
				right();
			else
				left();
		if(pos[0][0]==pos[num2][0])
			up(),left();
		else
			up();
		while(pz[n-1][n-2]!=num2)
			right(),down(),left(),up(),right();
	}
	while(pos[0][1]!=n-3)
		if(pos[0][1]<n-3)
			right();
		else
			left();
	if(pos[0][0]==n-1)
		up();
	right();
	while(pz[n-1][m]!=num2)
		left(),down(),right(),right(),up(),left(),left();
	down(),right();
}

void solve()
{
	int i, j;

	for(i = 0; i < n - 2; i++)
	{
		for(j = 0; j < n-1; j++)
			if(pz[i][j]!=i*n+j+1)
				push(i,j,0);
		if(pz[i][j]!=i*n+j+1)
			push(i,j,1);
	}
	for(i = 0; i < n-2; i++)
	{
		if(pz[n-2][i]!=(n-1)*(n-1)+i||pz[n-1][i]!=n*n-n+1+i)
			Push(i);
	}
	finish();
}

void input()
{
	int i, j;

	fscanf(bb,"%d",&n);
	p = 0;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			fscanf(bb,"%d",&pz[i][j]);
			pos[pz[i][j]][0] = i;
			pos[pz[i][j]][1] = j;
		}
	while(pos[0][0]!=n-1)
		Down();
	while(pos[0][1]!=n-1)
		Right();
	com[l] = '\0';
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			tmp[p++] = pz[i][j];
	if(check())
		printf("No Answer!");
	else
		printf("%s",com),solve();
}

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