骑士周游详解.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&&cvis[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;inx=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&&nyvis[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&&yreturn1;
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;jprintf("%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&&yreturn1;
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;jprintf("%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)的选择时,永远只选