poj 2488A knight'sjourneyDFS+回溯

题目链接：http://poj.org/problem?id=2488

题目大意：一个骑士从棋盘某一个点出发走“马”步，问能否刚好把图遍历一遍，如果有多种方法那么输出字典序最小的路径。

分析：1，确认起点，必须是A1，因为如果骑士能遍历一圈，那么它一定会经过A1,字典序最小的话那么就一定是从A1开始。

   2,骑士优先选择的方向，可以画一个一个图，那么画一个图可以确定以下顺序。int dy[8]={-2,-2,-1,-1,1,1,2,2},dx[8]={-1,1,-2,2,-2,2,-1,1};

   3，回溯！经典的回溯题目。

code:

#include<cstdio> #include<cstring> int visit[30][30]; int N,M,CASE; int dy[8]={-2,-2,-1,-1,1,1,2,2},dx[8]={-1,1,-2,2,-2,2,-1,1};//按优先级排列的8个方向 char ch[30]=" ABCDEFGHIJKLMNOPQRSTUVWXYZ";//打印时将数字转换为字母 struct node{int x,y;}a[1000];//结构体存走过的地方。 void print(){     printf("Scenario #%d:\n",++CASE);     printf("A1");     for(int i=1;i<M*N;++i)         printf("%c%d",ch[a[i].y],a[i].x);     printf("\n"); } bool dfs(int x,int y,int num){  // printf("x=%d,y=%d,num=%d\n",x,y,num);  if(num==M*N)return true;     for(int i=0;i<8;++i){         int nx=x+dx[i],ny=y+dy[i];         if(nx>=1&&nx<=N&&ny>=1&&ny<=M&&!visit[nx][ny]){             visit[nx][ny]=1;             a[num].x=nx,a[num].y=ny;            if(dfs(nx,ny,num+1))return true;            visit[nx][ny]=0;//回溯 //            printf("nx=%d,ny=%d,num=%d\n",nx,ny,num);         }     }     return false; } int main(void){     int T;scanf("%d",&T);     CASE=0;     while(T--){         scanf("%d%d",&N,&M);         memset(visit,0,sizeof(visit));         visit[1][1]=1;         if(dfs(1,1,1))print();         else printf("Scenario #%d:\nimpossible\n",++CASE);         if(T)printf("\n");     } }