POJ-2488 A Knight's Journey

POJ-2488 A Knight’s Journey

题目链接：

题目大意：给定一个大小的棋盘 问你能不能将棋盘上所有点踩且仅踩一次 如果可以 输出字典序最小的那种踩法 横行为数字 列数为字母 由于要字典序最小 所以要从A1开始

解题思路：dfs搜索即可 注意要按字典序最小输出 所以能走的八个点需要分下优先级 我写的有点麻烦了

代码块：

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

typedef pair<int, int> p;
int sum = 0;
int index = 0;
int arrA[50][50];
int xxx[8]={-1, 1, -2, 2, -2, 2, -1, 1};
int yyy[8]={-2, -2, -1, -1, 1, 1, 2, 2};
char res[50][2];
int pp,qq;
bool isU = false;
void dfs(int x, int y);
int main(){
	int n;
	cin>>n;
	for(int k = 1; k <= n; k++){
		cin>>pp>>qq;
		sum = pp * qq;
		cout<<"Scenario #"<<k<<":"<<endl;
		arrA[1][1] = 1;
		res[index][0] = (char)1 + '0';
		res[index++][1] = 'A';
		dfs(1,1);
		if(!isU) cout<<"impossible\n";
		index = 0;
		memset(arrA,0,sizeof(arrA));
		isU = false;
		sum = 0;
		if(k!=n)cout<<endl;
	}
	return 0;
}
void dfs(int x, int y){
	if(isU) return;
	if(index == sum){
		for(int i = 0; i < sum-1; i++){
			printf("%c%c",res[i][1], res[i][0]);
		}
		printf("%c%d",(char)y - 1 + 'A', x);
		cout<<endl;
		isU = true;
	}else{
		for(int i = 0; i < 8; i++){
			int xx = x + xxx[i];
			int yy = y + yyy[i];
			if(xx >= 1 && xx <= pp && yy >= 1 && yy <= qq && arrA[xx][yy] == 0){
				arrA[xx][yy] = 1;
				res[index][0] = (char)xx + '0';
				res[index++][1] = (char)yy-1 + 'A';
				dfs(xx,yy);
				index--;
				arrA[xx][yy] = 0;
			}
		}
	}
}