3044819_ac_0ms_408k.c

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

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

int n, m;
char str[8][8];
int rel[258][258], mark[8][8];
char ans[8][8];

int check(char ch,int N,int M)
{
	int i, j, m1, m2;

	m1 = m2 = 0;
	for(i = 1; i < N; i++)
	{
		for(j = 1; j <= m; j++)
		{
			if(rel[ch][str[i][j]]==1)
			{
				if(mark[i][j]==M)
					m1 = 1;
				else
					m2 = 1;
			}
			if(rel[ch][str[i][j]]==-1&&mark[i][j]==M)
				return 0;
		}
	}
	if(m2)
		return 0;
	if(m1)
		return 1;
	return -1;
}

int search(int M,int N)
{
	char ch;
	int i, v;

	if(M>m)
	{
		return 1;
	}
	if(N>n)
	{
		ans[M+1][1] = str[1][M+1];
		mark[1][M+1] = M+1;
		if(search(M+1,2))
			return 1;
		else
		{
			mark[1][M+1] = 0;
			return 0;
		}
	}
	for(i = 1; i <= m; i++)
	{
		if(mark[N][i])
			continue;
		ch = str[N][i];
		v = check(ch,N,M);
		if(v==0)
			continue;
		mark[N][i] = M;
		if(v==1)
		{
			ans[M][N] = ch;
			if(search(M,N+1))
				return 1;
			else
			{
				mark[N][i] = 0;
				return 0;
			}
		}
		if(v==-1)
		{
			ans[M][N] = ch;
			if(!search(M,N+1))
			{
				mark[N][i] = 0;
			}
			else
			{
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int t, i;
	int a, b, c, d;
	char op[2];

	scanf("%d",&t);
	while(t--)
	{
		memset(mark,0,sizeof(mark));
		scanf("%d%d",&n,&m);
		for(i = 1; i <= n; i++)
		{
			scanf("%s",&str[i][1]);
		}
		memset(rel,0,sizeof(rel));
		while(1)
		{
			scanf("%d%d%s%d%d",&a,&b,op,&c,&d);
			if(a==0)
			{
				break;
			}
			if(op[0]=='N')
				rel[str[a][b]][str[c][d]] = rel[str[c][d]][str[a][b]] = -1;
			else
				rel[str[a][b]][str[c][d]] = rel[str[c][d]][str[a][b]] = 1;
		}
		memset(ans,'\0',sizeof(ans));
		mark[1][1] = 1;
		ans[1][1] = str[1][1];
		search(1,2);
		for(i = 1; i <= m; i++)
			puts(&ans[i][1]);
		puts("");
	}
	return 0;
}