2253309_ole.c

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

# include <stdio.h>

int n;
int pz[11][11];
int pos[101][2];
int p, tmp[102];

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

	num = 0;
	for(i = 0; i < p; i++)
		for(j = i+1; j < p; j++)
			if(tmp[j]&&tmp[j]<tmp[i])
				num++;
	return num%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 push(int w, int h, int b)
{
	int num;

	num = w*n+h+1;
	if(b||pos[num][0]!=w)//不在目标行上
	{
		if(pos[num][1]==pos[0][1])//num和0在同一列
		{
			if(pos[0][1]==0)
				right();
			else
				left();
		}
		while(pos[num][0]!=pos[0][0])//num和0放在同一行上
			if(pos[num][0]>pos[0][0])
				down();
			else
				up();
		while(pos[num][1]!=pos[0][1]-1)//0放在num的右面
			if(pos[num][1]<pos[0][1]-1)
				left();
			else
				right();
		left();
		while(pos[num][1]!=n-1)//将num推到最右面
			if(pos[0][0]==n-1)
				up(),right(),right(),down(),left();
			else
				down(),right(),right(),up(),left();
		while(pos[num][0]!=w+b)//将num推到目标行上
			up(),right(),down(),left(),up();
	}
	if(!b)
	{
		if(pos[0][0]==w)
			down();
		while(pos[0][1]!=pos[num][1]-1)
			if(pos[0][1]>pos[num][1]-1)
				left();
			else
				right();
		while(pos[0][0]!=w+1)
			up();
		right();
		while(pz[w][h]!=w*n+h+1)
			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(int m)
{
	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||pz[n-1][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]+1)
				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]+1)
				right();
			else
				left();
		if(pos[0][0]==pos[num1][0])
			up();
		else
			up(),left();
		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(n-2);
}

void input()
{
	int i, j;

	scanf("%d",&n);
	p = 0;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			scanf("%d",&pz[i][j]);
			tmp[p++] = pz[i][j];
			pos[pz[i][j]][0] = i;
			pos[pz[i][j]][1] = j;
		}
	if(check())
		printf("No Answer!\n");
	else
		solve();
}

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