2657090_ac_31ms_76k.c

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

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

int visited[12][12];
int a, b, mark;
int mov[8][2] = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};

int valid(int i,int j)
{
	if (i<1||j<1||i>a||j>b)
		return 0;
	return 1;
}

void dfs(int i,int j,char way[])
{
	int k, m, l;
	int len;

	m = 1;
	if( mark )
		return ;
	len = strlen(way);
	for (k = 0; k < 8; k++)
	{
		if(mark)
			return ;
		if (valid(i+mov[k][0],j+mov[k][1])&&!visited[i+mov[k][0]][j+mov[k][1]])
		{
			m = 0;
			visited[i+mov[k][0]][j+mov[k][1]] = 1;
			way[len] = 'A'+j+mov[k][1]-1;way[len+1] = i+mov[k][0]+'0';way[len+2] = '\0';
			dfs(i+mov[k][0],j+mov[k][1],way);
			visited[i+mov[k][0]][j+mov[k][1]] = 0;
		}
	}
	if (m)
	{
		for (l = 1; l <= a; l++)
		{
			for (k = 1; k <= b; k++)
			{
				if (visited[l][k]==0)
					return ;
			}
		}
		mark = 1;
		printf("%s\n\n",way);
	}
}

int main()
{
	int t, cas;
	char str[100];

	scanf("%d",&t);
	cas = 1;
	while (t--)
	{
		scanf("%d%d",&a,&b);
		printf("Scenario #%d:\n",cas++);
		if (a==1&&b==1)
		{
			printf("A1\n\n");
			continue;
		}
		if (a==1||a==2||b==1||b==2)
		{
			printf("impossible\n\n");
			continue;
		}
		memset(visited,0,sizeof(visited));
		visited[1][1] = 1;mark = 0;
		strcpy(str,"A1");
		dfs(1,1,str);
		if (!mark)
		{
			printf("impossible\n\n");
		}
	}
	return 1;
}