pku2488.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

/*
	Author: Sempr
	Algorithm:DFS
	Date:2006-05-03
*/

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

int visit[26][26], pos[27][2];
int found;
int dis[8][2] = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
int M, N;

int In(int x, int y)
{
	return x >= 0 && y >= 0 && x < M && y < N;
}

void DFS(int x, int y, int t)
{
	int nx, ny, i;
	if (found)
	{
		return;
	}
	pos[t][0] = y;
	pos[t][1] = x;
	if (t == M * N)
	{
		found = 1;
		return;
	}
	for (i = 0; i < 8; i++)
	{
		nx = x + dis[i][1];
		ny = y + dis[i][0];
		if (In(nx, ny))
		{
			if (visit[nx][ny])
			{
				continue;
			}
			visit[nx][ny] = t + 1;
			DFS(nx, ny, t + 1);
			visit[nx][ny] = 0;
		}
	}
}

void Solve()
{
	int i, j, k;
	scanf("%d %d", &M, &N);
	memset(visit, 0, sizeof(visit));
	visit[0][0] = 1;
	found = 0;
	DFS(0, 0, 1);
	if (found)
	{
		for (i = 1; i <= M * N; i++)
		{
			printf("%c%c", 'A' + pos[i][0], '1' + pos[i][1]);
		}
	}
	else
	{
		printf("impossible");
	}
	printf("\n\n");
}

int main()
{
	int T, t;
	scanf("%d", &T);
	for (t = 0; t < T; t++)
	{
		printf("Scenario #%d:\n", t + 1);
		Solve();
	}
	return 0;
}