骑士周游详解.docx

骑士周游详解.docx

《骑士周游详解.docx》由会员分享，可在线阅读，更多相关《骑士周游详解.docx（22页珍藏版）》请在冰点文库上搜索。

骑士周游详解

AKnight'sJourney

TimeLimit:

1000MSMemoryLimit:

65536K

TotalSubmissions:

14944Accepted:

4991

Description

Background

Theknightisgettingboredofseeingthesameblackandwhitesquaresagainandagainandhasdecidedtomakeajourney

aroundtheworld.Wheneveraknightmoves,itistwosquaresinonedirectionandonesquareperpendiculartothis.Theworldofaknightisthechessboardheislivingon.Ourknightlivesonachessboardthathasasmallerareathanaregular8*8board,butitisstillrectangular.Canyouhelpthisadventurousknighttomaketravelplans?

Problem

Findapathsuchthattheknightvisitseverysquareonce.Theknightcanstartandendonanysquareoftheboard.

Input

Theinputbeginswithapositiveintegerninthefirstline.Thefollowinglinescontainntestcases.Eachtestcaseconsistsofasinglelinewithtwopositiveintegerspandq,suchthat1<=p*q<=26.Thisrepresentsap*qchessboard,wherepdescribeshowmanydifferentsquarenumbers1,...,pexist,qdescribeshowmanydifferentsquarelettersexist.ThesearethefirstqlettersoftheLatinalphabet:

A,...

Output

Theoutputforeveryscenariobeginswithalinecontaining"Scenario#i:

",whereiisthenumberofthescenariostartingat1.Thenprintasinglelinecontainingthelexicographicallyfirstpaththatvisitsallsquaresofthechessboardwithknightmovesfollowedbyanemptyline.Thepathshouldbegivenonasinglelinebyconcatenatingthenamesofthevisitedsquares.Eachsquarenameconsistsofacapitalletterfollowedbyanumber.

Ifnosuchpathexist,youshouldoutputimpossibleonasingleline.

SampleInput

3

11

23

43

SampleOutput

Scenario#1:

A1

Scenario#2:

impossible

Scenario#3:

A1B3C1A2B4C2A3B1C3A4B2C4

这道简单的题目竟然花了我一个晚上，本来相练习一下用权值来解决这道经典的骑士周游问题，没想到这道题用骑士周游的优化算法竟然超时（用自己的数据跑但是oj上是AC的），oj上跑了813ms下面是我的code：

#include

#include

#include

#definelne27

intp,q;

intx[lne],y[lne],ans_x[lne],ans_y[lne];

intder[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};

boolvis[lne][lne],flag;

typedefstructnode{

intp,v;

}cor;

boolcanjump（intr,intc）{

if（r>=0&&r=0&&c

vis[r][c]）

returntrue;

returnfalse;

}

intweight（intr,intc）{

inti,count;

for（i=count=0;i<8;i++）

if（canjump（r+der[i][0],c+der[i][1]））

count++;

returncount;

}

intcmp（constvoid*a,constvoid*b）{

cor*c=（cor*）a;

cor*d=（cor*）b;

returnc->v>d->v?

1:

-1;

}

voidbacktrace（intcur,intr,intc）{

inti,k,nx,ny;

if（cur==p*q）{

boolfl=false;

flag=false;

for（i=0;i

if（（ans_y[i]>y[i]）||（ans_x[i]>x[i]&&ans_y[i]==y[i]））{

fl=true;

break;

}

elseif（（ans_y[i]

break;

}

if（fl）

for（;i

ans_x[i]=x[i];

ans_y[i]=y[i];

}

return;

}

else{

cords[8];

for（i=k=0;i<8;i++）{

nx=r+der[i][0];

ny=c+der[i][1];

if（canjump（nx,ny））{

ds[k].v=weight（nx,ny）;

ds[k++].p=i;

}

}

qsort（ds,k,sizeof（ds[0]）,cmp）;

for（i=0;i

nx=r+der[ds[i].p][0];

ny=c+der[ds[i].p][1];

vis[nx][ny]=true;

x[cur]=nx;y[cur]=ny;

backtrace（cur+1,nx,ny）;

vis[nx][ny]=false;

}

}

}

voiddeal（）{

inti,j;

for（i=0;i

ans_x[i]=ans_y[i]=50;

vis[0][0]=true;

backtrace（1,0,0）;

}

voidoutput（）{

inti;

if（flag）puts（"impossible\n"）;

else{

for（i=0;i

printf（"%c%d",ans_y[i]+'A',ans_x[i]+1）;

puts（"\n"）;

}

}

intmain（void）{

intncase,i;

scanf（"%d",&ncase）;

for（i=1;i<=ncase;i++）{

memset（vis,false,sizeof（vis））;

scanf（"%d%d",&p,&q）;

printf（"Scenario#%d:

\n",i）;

flag=true;

deal（）;

output（）;

}

return0;

}

然而上面的代码对于8*8的棋盘还是有可行性的，纯粹是数据问题，呵呵

后来没办法只能用bfs或者dfs水过，但是由于这道题目只要求求最小字典序的那个结果所以用dfs就可以了，不出意外的话，这道题用dfs做，反而比bfs快，下面是AC的code  16ms ：

#include

#include

#include

#definelne27

intp,q;

intx[lne];

chary[lne];

intder[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};

boolvis[lne][lne];

boolbacktrace（intcur,intr,intc）{

inti,nx,ny;

if（cur==p*q-1）{

x[cur]=r;y[cur]=c+'A';

returntrue;

}

else{

for（i=0;i<8;i++）{

nx=r+der[i][0];

ny=c+der[i][1];

if（nx>=0&&nx=0&&ny

vis[nx][ny]）{

vis[nx][ny]=true;

x[cur]=r;y[cur]=c+'A';

if（backtrace（cur+1,nx,ny））

returntrue;

vis[nx][ny]=false;

}

}

}

returnfalse;

}

intmain（void）{

intncase,i;

scanf（"%d",&ncase）;

for（i=1;i<=ncase;i++）{

memset（vis,false,sizeof（vis））;

scanf（"%d%d",&p,&q）;

printf（"Scenario#%d:

\n",i）;

vis[0][0]=true;

if（backtrace（0,0,0））{

for（intj=0;j

printf（"%c%d",y[j],x[j]+1）;

putchar（'\n'）;

}

else

puts（"impossible"）;

if（i!

=ncase）putchar（'\n'）;

}

return0;

}

这是网上用bfs做的code:

#include

usingnamespacestd;

boolvisit[10][10],f;

intt,m,i,j,ans[100][2],x,y,p,q;

intmove[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};

voiddg（intp1,intq1,intans1）

{

visit[p1][q1]=true;

ans[ans1][0]=p1,ans[ans1][1]=q1;

if（ans1==p*q）

{

f=true;

for（i=1;i<=ans1;i++）

printf（"%c%d",（char）（（int）'A'+ans[i][1]-1）,ans[i][0]）;

printf（"\n"）;

return;

}

for（inti1=0;i1<8;i1++）

{

x=p1+move[i1][0],y=q1+move[i1][1];

if（x>0&&x<=p&&y>0&&y<=q）

{

if（visit[x][y]==false）

dg（x,y,ans1+1）;

if（f）return;

}

}

visit[p1][q1]=false;

return;

}

intmain（）

{

//freopen（"2488.in","r",stdin）;

//freopen（"2488.out","w",stdout）;

scanf（"%d",&m）;

t=0;

while（m--）

{

t++;

scanf（"%d%d",&p,&q）;

printf（"Scenario#%d:

\n",t）;

f=false;

memset（visit,0,sizeof（visit））;

dg（1,1,1）;

if（!

f）printf（"impossible\n"）;

if（m）printf（"\n"）;

}

return0;

}

下面是大牛写的骑士周游的三种方法但是最后的一种贪心是错的

/*

*File:

KnightTravel1.cpp

*Author:

eshow

*Date:

2007-09-10

*Question:

考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？

如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。

试设计一个算法找出这样一条马的周游路线。

*Solution:

使用回溯法，马每一步至多有8种跳法，遍历这8种跳法，得到结果。

这是一个子集树的回溯问题，每一个step[i]都在[0,7]之间。

设棋盘大小为N*N，则时间复杂度为O（8^（N*N）），当N=8时，算法很慢。

*/

#include

#include

#include

constintN=8;

intstep[N*N]={-1};

intchess[N][N]={0};

intJump[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};

intp=0;

intcanJump（intx,inty）

{

if（x>=0&&x=0&&y

return1;

return0;

}

voidBackTrace（intt,intx,inty）

{

if（t>=N*N）

{

p++;

for（inti=1;i<=N*N-1;++i）

{

printf（"%d",step[i]）;

}

printf（""）;

for（inti=0;i

{

for（intj=0;j

printf（"%2d",chess[i][j]）;

printf（""）;

}

printf（""）;

exit

（1）;

//return;

}

else

{

for（inti=0;i<8;++i）

{

if（canJump（x+Jump[i][0],y+Jump[i][1]））

{

x+=Jump[i][0];

y+=Jump[i][1];

chess[x][y]=t+1;

step[t]=i;

BackTrace（t+1,x,y）;

chess[x][y]=0;

x-=Jump[i][0];

y-=Jump[i][1];

}

}

}

}

intmain（）

{

intx=0;

inty=0;

chess[x][y]=1;

BackTrace（1,x,y）;

printf（"AllResultsNumber=%d",p）;

}

上述简单回溯算法的时间复杂度是O（8^（N*N）），因为每次都按照Jump定义的顺序遍历，因此在算某些点的时候会很慢。

可以考虑采用启发式的遍历规则：

即向前看两步，当每准备跳一步时，设准备跳到（x,y）点，计算（x,y）这一点可能往几个方向跳（即向前看两步），将这个数目设为（x,y）点的权值，将所有可能的（x,y）按权值排序，从最小的开始，循环遍历所有可能的（x,y），回溯求出结果。

算法可以求出所有可能的马跳棋盘路径，算出一个可行的结果很快，但在要算出所有可能结果时，仍然很慢，因为时间复杂度本质上并没有改变，仍为O（8^（N*N））。

下面是实现这一思想的代码：

/*

/*

*File:

KnightTravel2.cpp

*Author:

eshow

*Date:

2007-09-10

*Question:

考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？

如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。

试设计一个算法找出这样一条马的周游路线。

*Solution:

使用回溯法，马每一步至多有8种跳法，遍历这8种跳法，得到结果。

这是一个子集树的回溯问题，每一个step[i]都在[0,7]之间。

设棋盘大小为N*N，则时间复杂度为O（8^（N*N）），当N=8时，算法很慢。

优化：

当每准备跳一步时，设准备跳到（x,y）点，计算（x,y）这一点可能往几个方向跳（即向前看两步），将这个数目设为（x,y）点的权值，将所有可能的（x,y）按权值排序，从最小的开始，循环遍历所有可能的（x,y），回溯求出结果。

算法可以求出所有可能的马跳棋盘路径，算出一个可行的结果很快，但当N=8时，要计算所有可能的结果仍然很慢，原因是结果太多了。

BackTrace（）函数实现了这种思想。

#include

#include

#include

constintN=8;

intstep[N*N]={-1};

intchess[N][N]={0};

intJump[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};

intp=0;

intcanJump（intx,inty）

{

if（x>=0&&x=0&&y

return1;

return0;

}

intweightStep（intx,inty）

{

intcount=0;

for（inti=0;i<8;++i）

{

if（canJump（x+Jump[i][0],y+Jump[i][1]））

count++;

}

returncount;

}

voidinssort（inta[],intb[],intn）

{

if（n<=0）return;

for（inti=0;i

{

for（intj=i;j>0;--j）

{

if（a[j]

{

inttemp=a[j-1];

a[j-1]=a[j];

a[j]=temp;

temp=b[j-1];

b[j-1]=b[j];

b[j]=temp;

}

}

}

}

voidBackTrace（intt,intx,inty）

{

if（t>=N*N）

{

p++;

for（inti=1;i<=N*N-1;++i）

{

printf（"%d",step[i]）;

}

printf（""）;

for（inti=0;i

{

for（intj=0;j

printf（"%2d",chess[i][j]）;

printf（""）;

}

printf（""）;

exit

（1）;

//return;

}

else

{

intcount[8],possibleSteps[8];

intk=0;

for（inti=0;i<8;++i）

{

if（canJump（x+Jump[i][0],y+Jump[i][1]））

{

count[k]=weightStep（x+Jump[i][0],y+Jump[i][1]）;

possibleSteps[k++]=i;

}

}

inssort（count,possibleSteps,k）;

for（inti=0;i

{

intd=possibleSteps[i];

x+=Jump[d][0];

y+=Jump[d][1];

chess[x][y]=t+1;

step[t]=d;

BackTrace（t+1,x,y）;

chess[x][y]=0;

x-=Jump[d][0];

y-=Jump[d][1];

}

}

}

intmain（）

{

intx=0;

inty=0;

chess[x][y]=1;

BackTrace（1,x,y）;

printf（"AllResultsNumber=%d",p）;

}

/*

*File:

KnightTravel3.cpp

*Author:

eshow

*Date:

2007-09-10

*Question:

考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？

如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。

试设计一个算法找出这样一条马的周游路线。

*Solution:

如果不要求找出所有结果，可以使用贪心算法，在（x,y）的选择时，永远只选