2722616_ac_327ms_76k.c

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

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

int m, n, k;
int chess[27][27];

int valid(int a,int b)
{
	if(a<0||b<0||a>=m||b>=n)
		return 0;
	return 1;
}

int check()
{
	int i, j, k, num;
	int a, b;

	num = 0;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (!chess[i][j])
			{
				for (k = 0; k < n; k++)
				{
					if (chess[i][k])
						goto loop;
				}
				for (k = 0; k < m; k++)
				{
					if (chess[k][j])
						goto loop;
				}
				a = i;b = j;
				while(valid(a,b))
				{
					if(chess[a][b])
						goto loop;
					a++,b++;
				}
				a = i;b = j;
				while(valid(a,b))
				{
					if(chess[a][b])
						goto loop;
					a--,b--;
				}
				a = i;b = j;
				while(valid(a,b))
				{
					if(chess[a][b])
						goto loop;
					a--,b++;
				}
				a = i;b = j;
				while(valid(a,b))
				{
					if(chess[a][b])
						goto loop;
					a++,b--;
				}
				num++;
			}
loop:
			;
		}
	}
	return num;
}

int bigger(int a,int b,int c,int d)
{
	char t1[4], t2[4];

	t1[0] = a+'a';t2[0] = c+'a';
	itoa(b,&t1[1],10);
	itoa(d,&t2[1],10);
	if (strcmp(t1,t2)>0)
		return 1;
	else
		return 0;
}

int main()
{
	int i, j, t;
	int a, b, max;
	char tmp[4];

	max = -1;
	scanf("%d%d%d",&m,&n,&k);
	memset(chess,0,sizeof(chess));
	for (i = 0; i < k; i++)
	{
		scanf("%s",tmp);
		chess[tmp[0]-'a'][atoi(&tmp[1])-1] = 1;
	}
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (!chess[i][j])
			{
				chess[i][j] = 1;
				t = check();
				chess[i][j] = 0;
				if (t > max)
				{
					max = t;
					a = i;
					b = j+1;
				}
				if (t==max&&bigger(a,b,i,j+1))
				{
					a = i;
					b = j+1;
				}
			}
		}
	}
	printf("%c%d\n%d\n",a+'a',b,max);
	return 0;
}