2315.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2315 on 2006-08-13 at 22:19:32 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 8;
const int DIR[][2] = { { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, 
							{ 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } };

int n, m, path[N*N][2];
bool vst[N][N];

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && !vst[x][y]; }
void travel();
bool dfs(int, int, int);

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

void travel()
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(dfs(i, j, 0)) return;
	printf("impossible\n\n");
}
bool dfs(int x, int y, int step)
{
	path[step][0] = x; path[step][1] = y;
	if(step+1 == n*m) {
		for(int i = 0; i <= step; i++) printf("%c%d", path[i][0]+'A', path[i][1]+1);
		printf("\n\n"); return true;
	} else {
		vst[x][y] = true;
		for(int i = 0; i < 8; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(!legal(cx, cy)) continue;
			else if(dfs(cx, cy, step+1)) { vst[x][y] = false; return true; }
		}
		vst[x][y] = false; return false;
	}
}