125.cpp

来自「平时acm训练时ac的源代码」· C++ 代码 · 共 557 行

//125
//Accepted 31 ms 61 kb 

#include <stdio.h>

int find3N(int *A, int *B, int No)
{
	int t = 0, t2, z, t3;
	switch (No)
	{
	case 0:
	{
		for (z=0; z<=9-B[0]; z++)
		{
			A[0] = z;
			t = find3N(A, B, 1);
			if (1==t)
			{
				return 1;
			}
		}
		return -1;
	}
	case 1:
	{
		for (z=0; z<=9-B[1]; z++)
		{
			if (!(A[0]>z && B[1]<1))
			{
				A[1] = z;
				t = find3N(A, B, 2);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 2:
	{
		for (z=0; z<=9-B[2]; z++)
		{
			if (!(A[1]>z && B[2]<1))
			{
				A[2] = z;
				t = find3N(A, B, 3);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 3:
	{
		if (A[1]>A[0])
		{
			t2 = 1;
		}
		else
		{
			t2 = 0;
		}
		for (z=0; z<=9-B[3]; z++)
		{
			if (z>A[0])
			{
				t3 = t2 + 1;
			}
			else
			{
				t3 = t2;
			}
			if (!(A[0]>z && B[3]<1) && B[0]==t3)
			{
				A[3] = z;
				t = find3N(A, B, 4);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 4:
	{
		t2 = 0;
		if (A[0]>A[1])
		{
			t2 ++;
		}
		if (A[2]>A[1])
		{
			t2 ++;
		}
		int t4;
		for (z=0; z<=9-B[4]; z++)
		{
			if (A[3]>z)
			{
				t4 = 1;
			}
			else
			{
				t4 = 0;
			}
			if (z>A[1])
			{
				t3 = t2 + 1;
			}
			else
			{
				t3 = t2;
			}
			if (A[1]>z)
			{
				t4 ++;
			}
			if (t4<=B[4] && B[1]==t3)
			{
				A[4] = z;
				t = find3N(A, B, 5);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 5:
	{
		t2 = 0;
		if (A[1]>A[2])
		{
			t2 ++;
		}
		int t4;
		for (z=0; z<=9-B[5]; z++)
		{
			if (A[4]>z)
			{
				t4 = 1;
			}
			else
			{
				t4 = 0;
			}
			if (z>A[2])
			{
				t3 = t2 + 1;
			}
			else
			{
				t3 = t2;
			}
			if (A[2]>z)
			{
				t4 ++;
			}
			if (t4<=B[5] && B[2]==t3)
			{
				A[5] = z;
				t = find3N(A, B, 6);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 6:
	{
		if (A[4]>A[3])
		{
			t2 = 1;
		}
		else
		{
			t2 = 0;
		}
		if (A[0]>A[3])
		{
			t2 ++;
		}
		int t4;
		for (z=0; z<=9-B[6]; z++)
		{
			if (z>A[3])
			{
				t3 = t2 + 1;
			}
			else
			{
				t3 = t2;
			}
			if (A[3]>z)
			{
				t4 = 1;
			}
			else
			{
				t4 = 0;
			}
			if (t4<=B[5] && B[3]==t3)
			{
				A[6] = z;
				t = find3N(A, B, 7);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 7:
	{
		int t6, t6t, t4, t4t;
		if (A[3]>A[6])
		{
			t6 = 1;
		}
		else
		{
			t6 = 0;
		}
		if (A[1]>A[4])
		{
			t4 = 1;
		}
		else
		{
			t4 = 0;
		}
		if (A[3]>A[4])
		{
			t4++;
		}
		if (A[5]>A[4])
		{
			t4++;
		}
		int t7;
		for (z=0; z<=9-B[7]; z++)
		{
			if (z>A[6])
			{
				t6t = t6+1;
			}
			else
			{
				t6t = t6;
			}
			if (z>A[4])
			{
				t4t = t4+1;
			}
			else
			{
				t4t = t4;
			}
			if (A[4]>z)
			{
				t7 = 1;
			}
			else
			{
				t7 = 0;
			}
			if (A[6]>z)
			{
				t7++;
			}
			if (t7<=B[7] && B[4]==t4t && B[6]==t6t)
			{
				A[7] = z;
				t = find3N(A, B, 8);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 8:
		int t5, t5t, t7, t7t;
		if (A[2]>A[5])
		{
			t5 = 1;
		}
		else
		{
			t5 = 0;
		}
		if (A[4]>A[5])
		{
			t5++;
		}
		if (A[4]>A[7])
		{
			t7 = 1;
		}
		else
		{
			t7 = 0;
		}
		if (A[6]>A[7])
		{
			t7 ++;
		}
		for (z=0; z<10-B[8]; z++)
		{
			if (z>A[5])
			{
				t5t = t5+1;
			}
			else
				t5t = t5;
			if (z>A[7])
			{
				t7t = t7+1;
			}
			else
				t7t = t7;
			if (A[5]>z)
			{
				t2 = 1;
			}
			else
			{
				t2 = 0;
			}
			if (A[7]>z)
			{
				t2++;
			}
			if (t7t==B[7] && t5t==B[5] && t2==B[8])
			{
                A[8] = z;
				return 1;
			}
		}
		return -1;
	}
	return 0;
}

int find2N(int *A, int *B, int No)
{
	int z, t;
	switch (No)
	{
	case 0:
	{
		for (z=0; z<=9-B[0]; z++)
		{
			A[0] = z;
			t = find2N(A, B, 1);
			if (1==t)
			{
				return 1;
			}
		}
		return -1;
	}
	case 1:
	{
		int t2;
		for (z=0; z<=9-B[1]; z++)
		{
			if (A[0]>z)
			{
				t2 = 1;
			}
			else
			{
				t2 = 0;
			}
			if (t2<=B[1])
			{
				A[1] = z;
				t = find2N(A, B, 2);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 2:
	{
		int t1, t1t, t2;
		if (A[1]>A[0])
		{
			t1 = 1;
		}
		else
		{
			t1 = 0;
		}
		for (z=0; z<=9-B[2]; z++)
		{
			if (z>A[0])
			{
				t1t = t1+1;
			}
			else
			{
				t1t = t1;
			}
			if (A[0]>z)
			{
				t2 = 1;
			}
			else
			{
				t2 = 0;
			}
			if (t2<=B[2] && t1t==B[0])
			{
				A[2] = z;
				t = find2N(A, B, 3);
				if (1==t)
				{
					return 1;
				}
			}
		}
		return -1;
	}
	case 3:
	{
		int t1, t1t, t2, t2t, t3;
		if (A[0]>A[1])
		{
			t1 = 1;
		}
		else
		{
			t1 = 0;
		}
		if (A[0]>A[2])
		{
			t2 = 1;
		}
		else
		{
			t2 = 0;
		}
		for (z=0; z<=9-B[3]; z++)
		{
			if (z>A[1])
			{
				t1t = t1+1;
			}
			else
			{
				t1t = t1;
			}
			if (z>A[2])
			{
				t2t = t2+1;
			}
			else
			{
				t2t = t2;
			}
			if (A[1]>z)
			{
				t3 = 1;
			}
			else
			{
				t3 = 0;
			}
			if (A[2]>z)
			{
				t3++;
			}
			if (t3==B[3] && t2t==B[2] && t1t==B[1])
			{
				A[3] = z;
				return 1;
			}
		}
		return -1;
	}
	}
	return 0;
}

int main(void)
{
	int N, i, B[9], A[9];
	scanf("%d", &N);
	for (i=0; i<N*N; i++)
	{

		scanf("%d", &B[i]);
	}
	if (N==1)
	{
		if (B[0]==0)
		{
			printf("0");
		}
		else
		{
			printf("NO SOLUTION");
		}
	}
	else if (3==N)
	{
		if (1 == find3N(A, B, 0))
		{
			for (i=1; i<=9; i++)
			{
				printf("%d ", A[i-1]);
                if (i%3==0)
                {
					printf("\n");
                }
			}
		}
		else
		{
			printf("NO SOLUTION");
		}
	}
	else
	{
		if (1 == find2N(A, B, 0))
		{
			for (i=1; i<=4; i++)
			{
				printf("%d ", A[i-1]);
                if (i%2==0)
                {
					printf("\n");
                }
			}
		}
		else
		{
			printf("NO SOLUTION");
		}
	}
	return 0;
}