马踏棋盘、骑士周游、骑士漫游问题（回溯法、深度优先搜索、哈密尔顿路径）

小甲鱼

题目渊源：

马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。

题目要求：

• 国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。
• 编写代码，实现马踏棋盘的操作，要求用1~64来标注“马”移动的路径。
  

视频讲解：http://blog.fishc.com/2554.html

源代码参考：http://bbs.fishc.com/thread-31690-1-1.html

1132719438

强烈支持楼主ing……

四季如春へ★

poj2488 骑士遍历问题
dfs
#include<iostream>
#include<stdio.h>
using namespace std;

int dpy[8]={-1,1,-2,2,-2,2,-1,1},dpx[8]={-2,-2,-1,-1,1,1,2,2};
int visit[30][30],path[50][2],tx,ty,v;
bool dfs(int x,int y,int step)
{
        for(int i=0;i<8;i++)
        {
        int x1=x+dpx[i],y1=y+dpy[i];
                if(x1>=1&&x1<=tx&&y1>=1&&y1<=ty&&visit[x1][y1]==0&&v<tx*ty)
                {
                        path[step][0]=x1;
                        path[step][1]=y1;
                        v++;
                        visit[x1][y1]=1;
                        dfs(x1,y1,step+1);
                        if(v==tx*ty)
                            return true;
                        visit[x1][y1]=0;
                    v--;
                }
        }
}
int main()
{
        int cas,n=0;
        cin>>cas;
        while(cas--)
        {
                n++;
                v=1;
                memset(visit,0,sizeof(visit));
                memset(path,0,sizeof(path));
                cin>>ty>>tx;
                path[0][0]=1;
                path[0][1]=1;
                visit[1][1]=1;
                dfs(1,1,1);
                printf("Scenario #%d:\n",n);
                if(path[tx*ty-1][0]!=0)
                {
                        for(int i=0;i<tx*ty;i++)
                        {
                                cout<<(char)(path[i][0]+64)<<path[i][1];
                        }
                }
                else
                {
                        cout<<"impossible";
                }
                cout<<endl<<endl;
        }
        return 0;
}

大娱乐家_╮

强烈支持楼主ing……

岁月如歌

我只是路过打酱油的。

2004111

激动人心，无法言表！

2004111

真是被感动的痛哭流涕……

牡丹花下死做鬼

我真的很感悟……

aicode

强烈支持楼主ing……

THE

        int sum=0;

lf19891031

强烈支持楼主ing……

xmhh0425@163.co

四季如春へ★ 发表于 2013-7-15 19:27
poj2488 骑士遍历问题
dfs
#include

这是用什么方法解的？？？

@XXA

嗯呐

兜抖逗豆豆

kaka