POJ 2488(DFS)

タイトルリンク:http://poj.org/problem?id=2488
チェスでは、碁盤の上にずっと馬を置いて、「日」の字形で歩いて、碁盤の上のすべての位置を歩くことができるかどうか、起点と終点は任意で、経路があれば、辞書を出力するには最小の1つが必要です.
タイトルは简単に见えますが...长い间、辞书顺の问题に悩んで、検索方向の顺番性に注意して、枚挙を避けることができます.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=30;
int T,n,m;
int map[maxn][maxn];
bool vis[maxn][maxn];
bool flag;

struct node{//    
	int x,y;
}a[maxn*maxn];

int dx[]={-2,-2,-1,-1,1,1,2,2};//         
int dy[]={-1,1,-2,2,-2,2,-1,1};

bool judge_State(int x,int y){
	if(x<0||x>=n||y<0||y>=m) return false;
	if(vis[x][y]) return false;
	if(flag) return false;
	return true;
}

void dfs(int x,int y,int step){
	if(step==n*m){
		for(int i=0;i<step;i++){
			printf("%c%d",a[i].x+'A',a[i].y+1);
		}
		putchar(10);
		flag=true;
		return ;
	}
	for(int i=0;i<8;i++){
		int ex=x+dx[i];
		int ey=y+dy[i];
		if(judge_State(ex,ey)){
			vis[ex][ey]=1;
			a[step].x=ex,a[step].y=ey;
			dfs(ex,ey,step+1);
			vis[ex][ey]=0;
		}
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	int cas=1;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&m,&n);
		printf("Scenario #%d:
",cas++);
		flag=false;
		memset(vis,0,sizeof(vis));
		vis[0][0]=1;
		dfs(0,0,1);
		if(!flag) puts("impossible");
		putchar(10);
	}
	return 0;
}