论坛 › 数据结构与算法 › 马踏棋盘、骑士周游、骑士漫游问题（回溯法、深度优先搜索、哈密尔顿路径）

小甲鱼 发表于 2013-5-16 17:35:49

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

题目渊源：

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

题目要求：



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

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

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

1132719438 发表于 2013-7-14 21:42:15

强烈支持楼主ing……

四季如春へ★ 发表于 2013-7-15 19:27:37

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

int dpy={-1,1,-2,2,-2,2,-1,1},dpx={-2,-2,-1,-1,1,1,2,2};
int visit,path,tx,ty,v;
bool dfs(int x,int y,int step)
{
        for(int i=0;i<8;i++)
        {
      int x1=x+dpx,y1=y+dpy;
                if(x1>=1&&x1<=tx&&y1>=1&&y1<=ty&&visit==0&&v<tx*ty)
                {
                        path=x1;
                        path=y1;
                        v++;
                        visit=1;
                        dfs(x1,y1,step+1);
                        if(v==tx*ty)
                          return true;
                        visit=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=1;
                path=1;
                visit=1;
                dfs(1,1,1);
                printf("Scenario #%d:\n",n);
                if(path!=0)
                {
                        for(int i=0;i<tx*ty;i++)
                        {
                                cout<<(char)(path+64)<<path;
                        }
                }
                else
                {
                        cout<<"impossible";
                }
                cout<<endl<<endl;
        }
        return 0;
}

大娱乐家_╮ 发表于 2013-7-24 13:07:10

强烈支持楼主ing……

a764934018 发表于 2013-8-7 19:29:18

岁月如歌 发表于 2013-11-27 16:54:42

我只是路过打酱油的。

2004111 发表于 2014-1-21 11:46:12

激动人心，无法言表！

2004111 发表于 2014-1-21 13:03:38

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

牡丹花下死做鬼 发表于 2014-2-1 21:59:37

我真的很感悟……

aicode 发表于 2014-4-25 11:36:02

强烈支持楼主ing……

THE 发表于 2014-5-4 22:51:12

        int sum=0;

lf19891031 发表于 2014-5-9 17:02:49

强烈支持楼主ing……

xmhh0425@163.co 发表于 2015-1-8 22:55:37

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


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

@XXA 发表于 2018-2-10 09:36:59

嗯呐

兜抖逗豆豆 发表于 2019-11-23 17:00:16

kaka

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