poj2488——A Knight's Journey

44424742

深搜！可剪枝！
以后，写深搜的时候，最好用flag标记下，而且，回溯的时候，应采用本题写法！
#include<stdio.h>#include<string.h>int dir[][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};bool map[30][30],flag;char path[100];int p,q;void dfs(int x,int y,int sum,int top){if(flag)return ;int i,tempx,tempy;if(sum==p*q){flag=true;return ;}for(i=0;i<8;i++){tempx=x+dir[i][0];tempy=y+dir[i][1];if(1<=tempx&&tempx<=q&&1<=tempy&&tempy<=p){if(map[tempx][tempy]){map[tempx][tempy]=false;path[top+1]=tempx-1+'A';path[top+2]=tempy+'0';dfs(tempx,tempy,sum+1,top+2);if(flag==false){    map[tempx][tempy]=true;}else return ;}}}}int main(){int T,i,sum,top;scanf("%d",&T);for(i=1;i<=T;i++){scanf("%d%d",&p,&q);sum=0;top=1;flag=false;printf("Scenario #%d:\n",i);memset(map,true,sizeof(map));map[1][1]=false;sum=1;path[1]='A';path[2]='1';top=2;dfs(1,1,sum,top);if(flag)for(int k=1;k<=p*q*2;k++)printf("%c",path[k]);else printf("impossible");printf("\n\n");}return 0;