鱼C论坛

 找回密码
 立即注册
查看: 10352|回复: 14

[技术交流] 马踏棋盘、骑士周游、骑士漫游问题(回溯法、深度优先搜索、哈密尔顿路径)

[复制链接]
发表于 2013-5-16 17:35:49 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目渊源:

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


题目要求:


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

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

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

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-7-14 21:42:15 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-15 19:27:37 | 显示全部楼层
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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-24 13:07:10 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2013-8-7 19:29:18 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-11-27 16:54:42 | 显示全部楼层
我只是路过打酱油的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-1-21 11:46:12 | 显示全部楼层
激动人心,无法言表!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-1-21 13:03:38 | 显示全部楼层
真是被感动的痛哭流涕……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-2-1 21:59:37 | 显示全部楼层
我真的很感悟……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-4-25 11:36:02 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-5-4 22:51:12 | 显示全部楼层
        int sum=0;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-5-9 17:02:49 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-1-8 22:55:37 | 显示全部楼层
四季如春へ★ 发表于 2013-7-15 19:27
poj2488 骑士遍历问题
dfs
#include

这是用什么方法解的???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-10 09:36:59 | 显示全部楼层
嗯呐
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-11-23 17:00:16 | 显示全部楼层
kaka
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 22:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表