44424742 发表于 2013-1-26 13:37:41

poj2488——A Knight's Journey

深搜!可剪枝!
以后,写深搜的时候,最好用flag标记下,而且,回溯的时候,应采用本题写法!
#include<stdio.h>#include<string.h>int dir[]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};bool map,flag;char path;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;tempy=y+dir;if(1<=tempx&&tempx<=q&&1<=tempy&&tempy<=p){if(map){map=false;path=tempx-1+'A';path=tempy+'0';dfs(tempx,tempy,sum+1,top+2);if(flag==false){    map=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=false;sum=1;path='A';path='1';top=2;dfs(1,1,sum,top);if(flag)for(int k=1;k<=p*q*2;k++)printf("%c",path);else printf("impossible");printf("\n\n");}return 0;
页: [1]
查看完整版本: poj2488——A Knight's Journey