POJ 2488 A Knight's Journey

题意：给一个p*q的棋盘，问你能不能遍历整个棋盘的每一个方格，如果能输出路径，不能则impossible.? 简单的深度遍历，得看看0msAC的有什么不同，这个是32ms,在输出时注意先输出列再输出行，例用大写字母表示结果按字典序排序，所有在遍历的时候先要从列小的开始。

代码：

[cpp]
#include?
using namespace std;?
int d[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};?
bool visit[30][30],success;?
int n,m,k,path[30][2];?
bool Judge(int i,int j)?
{?
???? if(i>=0&&j>=0&&i ???? return false;?
}?
bool Mark()?
{?
???? for(int i=0; i ????? for(int j=0; j ????????? if( !visit[i][j])?
??????????? return false;???
????? return true;?
}?
void Search(int x,int y)?
{?
???? int i,px,py,flag;?
???? visit[x][y]=true;?
??? // printf("%d %d\n",x,y);?
???? for( i=0,flag=0; i<8&&!success; i++){?
????????? px=x+d[i][0];?
????????? py=y+d[i][1];?
????????? if( Judge(px,py)&&!visit[px][py]){?
????????????? flag=1;?
????????????? Search(px,py);?
????????? }?
???? }?
???? if( !flag&&Mark()){?
????? //? printf("%d? %d\n",x,y);?
???????? success=true;?
???? }?
???? if( !success)?
???????? visit[x][y]=false;?
???? else{?
????????? path[k][0]=x;?
????????? path[k][1]=y;?
????????? k++;?
???? }?
}?
int main()?
{?
??? int t,i,j;?
??? scanf("%d",&t);?
??? for(int ca=1; ca<=t; ca++){?
??????????? success=false;?
??????????? scanf("%d%d",&n,&m);?
??????????? printf("Scenario #%d:\n",ca);?
??????????? memset(path,0,sizeof(path));?
??????????? memset(visit,false,sizeof(visit));?
??????????? k=0;?
??????????? if( n==1&&m!=1||m==1&&n!=1)?
??????????????? printf("impossible");?
??????????? else{?
???????????????? for( i=0; i ????????????????????? for( j=0; j ?????????????????????????? Search(j,i);?
?????????????????????????? if( success)?
?????????????????????????????? break;?
????????????????????? }?
???????????????? }?
???????????????? if( !success)?
???????????????????? printf("impossible");?
???????????????? else{?
????????????????????? for( i=k-1; i>=0; i--)?
?????????????????????????? printf("%c%d",'A'+path[i][1],path[i][0]+1);?
???????????????? }?
??????????? }?
??????????? printf("\n\n");?
??? }?
}?

?