数据结构与算法之骑士遍历 5C
 public class KnightNode {

    private int x;
    private int y;

    public KnightNode(int x,int y){
        this.x = x;
        this.y= y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}
 public class KnightTravels_2 {
    //row和col表示某个坐标走“日”的八个方向
    private static int row[] = {-2,-1,1,2,2,1,-1,-2};
    private static int col[] = {1,2,2,1,-1,-2,-2,-1};
    //每行数据表示一个坐标的8个方向是否有访问过。
    private boolean visited[][] = new boolean[64][8];
    //存储走过的位置
    public LinkedList list = new LinkedList();
    //8*8的棋盘
    protected int[][] matrix = new int[8][8];
    protected int step = 1;
    //x,y表示初始结点
    public void travel(int x,int y){
        while(step < 64){
            int newX = x;
            int newY = y;
            boolean hasNext = false;//标志当前位置(x,y)是否可以找到下一个位置
            for(int i = 0;i < 8;i++){
                newX = x + row[i];
                newY = y + col[i];
                if(newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && !visited[step-1][i] && matrix[newX][newY] == 0){
                    //符合条件:在边界内,且没有访问过
                    //如果可以找到符合条件的下一位置,就将当前位置压入链表,并设置找到的下一位置为当前位置
                    list.add(new KnightNode(x,y));
                    visited[step-1][i] = true;
                    matrix[x][y] = step++;
                    hasNext = true;
                    x = newX;
                    y = newY;
                    break;
                }
                visited[step-1][i] = true;
            }
            if(!hasNext && !list.isEmpty()){
                //如果找不到,就拿到栈顶的元素,从之前找过的方向开始找下一位置,
                matrix[x][y] = 0;
                KnightNode last = (KnightNode) list.getLast();
                x = last.getX();
                y = last.getY();
                list.removeLast();
                visited[step-1] = new boolean[8];
                step--;
            }
        }
    }

    public static void main(String args[]){
        KnightTravels_2 travel = new KnightTravels_2();
        //travel.travel(0,0);
        travel.travel(6,7);
        for(int i = 0;i < travel.matrix.length;i++){
            for(int j = 0;j < travel.matrix[i].length;j++){
                System.out.print(String.format("%4d",travel.matrix[i][j]));
            }
            System.out.println();
        }
    }   
}

大家看看有什么问题,为什么执行效率很差,执行的开始位置是(0,0)时可以打印出结果,但是进入while方法几百万次,其他开始位置陷入了无限循环,不知道是真的需要这么久,还是有个死循环在里面。

0

2个回答

2
u012734723
bluesnail95 谢谢分享
一年多之前 回复

一共就64个点,你想让它以日字格的形式走个遍,就算有可能做到,但是通过路线的点又不让它走,你自己想想它有可能走到step>=64吗,自然就一直循环了。

1
qq_27718453
庄粟 死循环了-_-!
一年多之前 回复
u012734723
bluesnail95 当我从(0,0)开始遍历的时候是可以找到解的,但是进入了while循环几百万次,怎么会进入这么多,
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C语言-数据结构-骑士周游-马踏棋盘问题-源代码
1. 目标 对于一个指定的起始坐标,按照‘马’的走棋规则,从该坐标开始搜索一条可以覆盖棋盘每个位置的走棋路径。例如下面是从(2,0)坐标开始搜索得到的一个解。 2. 代码结构 3. 源代码 该代码仅仅是寻找到一条生路,即停止。另外对选择的起始点,和寻找下一点的顺序不同(即sposition()中case的顺序不同,对于程序执行的时间影响会很大)。 另外程序中调用了time
图的周游和遍历
实验要求: 以邻接矩阵或邻接表为存储结构,建立连通无向图或有向图,并完成以下操作: (1)     深度优先遍历。 (2)     广度优先遍历。   实验代码: #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;malloc.h&amp;gt; #include&amp;lt;string.h&amp;gt; #define  M   100 t...
[算法]图算法之骑士遍历问题(象棋中马的遍历问题)分析,C语言实现
今天再讲点跟N皇后有关的问题,骑士遍历问题,或者象棋中马的遍历问题,当然这里的马是国际象棋了,两者有着很多相似点,同时又有很多不同点,主要还是限制路径的区别,N皇后主要是自由放置只要满足条件就好,马的遍历则跟上下遍历的路径有关了,主要运用了图算法之深度广度遍历,以及图的建立等算法。要求:实现棋盘上任意位置的一个棋子马,使它不重复的走过棋盘上的每一个棋盘格分析:首先知道马在棋盘是怎么走的,根据国际象
数据结构与算法10:马踏棋盘问题(骑士周游问题)
问题描述:在一个国际象棋的棋盘上,一个马按照它的规则如何才能从一个点出发遍历每一个位置,且每个点只访问一次。     问题分析:这是一个深搜的问题,沿着一条路前进直到遍历全部的点,那就完成了整个的过程。如果不行,就回退一步,换个方向继续前进。这可以用递归很方便地实现。注意到马在某个位置最多有8个方向可以走,因此需要对这8个方向进行试探。当然这8个方向不一定都存在,比如在边缘可能就会少一些
马的遍历/骑士问题 回溯算法 算法设计作业
马的遍历,骑士问题,马踏棋盘。回溯算法的经典问题,还有八皇后等。马的遍历也是一个。上算法课正好有这个问题,找了下能用的,vc++6.0调试可用
骑士周游遍历系统/C++
这是一个采用C++编写的、采用回溯法编写的骑士周游(马周游)遍历棋盘(8*8)的程序。本软件采用MFC编写,用户可看到骑士动态遍历棋盘的过程。
骑士遍历-c++,用穷举法可以得到所有遍历结果
经典的骑士遍历算法,可以设置棋盘的大小,结果返回骑士的遍历路线
数据结构经典算法(7)骑士走棋盘
说明:骑士旅游(Knighttour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出 已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完[所有的位 置? 解法:骑士的走法,基本上可以使用递回来解决,但是纯綷的递回在维度大时相当没有效率,  一个聪明的解法由J .C. Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路 就宽广了,骑士
回溯算法之骑士旅行问题
回溯法不同于纯暴力的瞎走,它通过不断的试探,层次变化,攻击问题,实现”保留现有信息“高效作战。 骑士旅行问题: 在N*N的国际象棋棋盘中有一个骑士在一角,问能否通过类似于中国象棋中马的走法走完所有的格子。所有的格子只能走一次。 最开始一看这个问题觉得,啊,这不就是个深度优先搜索吗,随便写写。 嗯,我的噩梦就这样开始了。处理好越界,访问格子,回溯等问题后,程序就是死循环!
bfs 经典例题:骑士游历
我们先来了解一下宽度优先搜索算法:   宽度优先搜索又译为广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点...
骑士游历算法
骑士游历,算法
骑士周游列国回溯递归解法
在一张国际象棋棋盘上(8*8方格),骑士(knight,马)位于任意一个位置。问如何才能让骑士不重不漏的经过棋盘上的每个格?本问题中已知骑士位置(m,n),其中0=<m,n<=8,要求给出骑士行走路径,路径可用8*8矩阵输出,其中值表示骑士到达此位置行走的步数(初始为1);
经典游戏算法之骑士走棋盘
问题描述:中国象棋中,马可以走遍棋盘上的任何角落.国际象棋中,也同样有这样的说法:骑士可以走遍棋盘上的每个格子.现在的问题是:在一个8x8的棋盘上,从任意位置开始,骑士如何可以不重复地走完所有的位置?   骑士在每一步都有8种可能的下一步走法(边界上除外),为了提高效率,可以选择所要走的下一步为下一步要选择时所能走的步数最少的一步.   函数说明: bool trav
C语言数据结构算法实现图的遍历
A 深度优先遍历:1.深度优先遍历的递归定义   假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通(从源点可达)的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未...
骑士周游问题源码
骑士周游问题,采用多种方法解决骑士周游问题,如有其它需要,请留言
马踏棋盘算法(骑士周游问题)
一、马踏棋盘算法 1、国际象棋的棋盘为8*8的方格棋盘,将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。 2、关于国际象棋“马”的走法:以“日”字为单位往斜对角上的那个方格走。如下图所示马在当前位置就有8种走法,如果不考虑边缘的特殊情况,那么需要8^64的时间复杂度才可以把整个棋盘的一个正确路径找出来。
递归——骑士巡游问题
问题 h: 【递归入门】骑士巡游问题 时间限制: 1 Sec  内存限制: 128 MB 提交: 23  解决: 14 [提交][状态][讨论版][命题人:外部导入] 题目描述 输入 n ( 1&amp;lt; = n &amp;lt; = 10 ) 代表棋盘的规模就是 n*n 的规模,骑士永远从 (1,1) 出发,要求骑士走遍所有棋盘的格子 输出 骑士的走法(遍历棋盘的所有格子)  注意方向: con...
骑士遍历问题
问题描述:跳马问题也称骑士遍历、马踏棋盘问题:在n*n方格的棋盘上,从任意指定的方格出发,为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
骑士周游问题(暴力解决:回溯法)
建议测试数据 3 0 或 4 0
骑士遍历
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboa...
每天刷个算法题20160523:骑士巡游的递归转非递归解法
为了防止思维僵化,每天刷个算法题。这里是骑士巡游的递归转非递归解法。
[算法设计与分析] 回溯法求解骑士问题/马周游问题 (C++)
实验课程:算法分析与设计 实验名称:回溯法的应用[骑士问题] (综设型实验)   第一部分 实验内容 1.实验目标 (1)熟悉使用回溯法求解问题的基本思路。 (2)掌握回溯算法的程序实现方法。 (3)理解回溯算法的特点。 2.实验任务 (1)从所给定的题目中选择一题,使用回溯法求解之。 (2)用文字来描述你的算法思路,包括解空间、限界函数、算法主要步骤等。 (3)使用C/C+...
骑士遍历C语言
骑士遍历c 预压表示 #include<stdio.h> #define LONG 5 int map [LONG][LONG]={0}; //地图的定义 int moveX[8]={2,2,1,1,-1,-1,-2,-2}; //X方向上的移动 int moveY[8]={1,-1,2,-2,2,-2,1,-1};
算法思考--------骑士走棋盘(c语言)
一、规则说明              骑士可以从任意一个位置出发,走法和中国象棋的"马"走法类似,"走日"。问:如何走完所有的位置 二、解法          可以用递归的方法解决,但是纯粹的递归在维度大时没有效率。一个聪明的解法由J.C.Warnsdorft提出:先将最难的位置走完,接下来的路就宽广了 三、代码实现 #include int travel(int x, int
八皇后和骑士遍历
八皇后问题是大数学家高斯于1850年提出来的。该问题是在8×8的国际象棋棋盘上放置8个皇后,使得没有一个皇后能"吃掉"任何其他一个皇后,即没有任何两个皇后被放置在棋盘的同一行、同一列或同一斜线上。要求编一个程序求出该问题的所有解。骑士游历问题是放在8×8的国际象棋棋盘上的一个马,按照马走"日"字的规则是否能够不重复地走遍棋盘的每个格。要求编一个程序求出该问题的一个解。l 解题思路使用回溯算法求解的
【DFS】(一)最简单的递归dfs——水坑问题(poj2386)
简单
POJ 1915 Knight Moves 骑士遍历问题(跳马问题)
1、对于这道题,我首先根据宽度优先搜索
基于Java的dfs+预见算法解决骑士游历问题
题目 骑士游历 骑士游历问题是指,在国际象棋的棋盘(8行*8列)上,一个马要遍历棋盘,即走到棋盘上的每一格,并且每隔只到达一次。设码在棋盘的某一位置(x,y)上,按照“走马日”的规则,下一步有8个方向走,如图所示。若给定起始位置(x0,y0),使用站和队列探索出一条马遍历棋盘的路径。 8 1 7 2
【深度优先搜索】骑士游历I
骑士游历I 题目 如下图所示有m*n一个棋盘,在棋盘左下角的A(1,1)点,有一个中国象棋〈马〉,并约定马走的规则: ①走日字;②只能向右走。 输入 两个整数,m,n (n,m&amp;amp;lt;=15) 输出 一个整数(最段的路线步数) 输入样例 9 8 输出样例 10 解题思路 用深度优先搜索来用最优化来进行搜索 #include&amp;amp;lt;iostream&amp;amp;gt; #include&amp;amp;lt;cstdio&amp;amp;.
【数据结构和算法】全面剖析树的各类遍历方法
面试中常考到树的前序,中序,后序和层序遍历,这篇博文就带你深度剖析一下二叉树的各类遍历算法的实现二叉树的遍历主要有四种,前序、中序、后序和层序遍历的实现方式主要是:递归和非递归递归遍历的实现非常容易,非递归的实现需要用到栈,难度系数要高一点。一、二叉树节点的定义二叉树的每个节点由节点值、左子树和右子树组成。class TreeNode{ public: int val; TreeNo
ACM:搜索算法专题(2)——骑士问题
题目描述:     在国际象棋的棋盘上放置3个骑士的棋子,按照骑士的移动规则移动这3个棋子,使其到达同一个位置,求最少的移动次数。 解答:     本题不难。首先说明一下国际象棋的规则,棋盘由8×8=64个黑白相间的格子组成,棋子放在某一个格子中。采用二维坐标的方式表示棋盘中的每一个格子,其中水平方向从左到右用 A-H 这8个英文字母表示,竖直方向从下到上用 1-8 这8个数字表示,
C++ 马踏棋盘(骑士周游)
马踏棋盘,用1枚马走遍棋盘。我用一个二维数组记录模拟的整个路径,x为列,y为行,以顺时针的方式寻找下一格,算法比较简单,就通过递归和循环回溯即可,就是如果是8*8的数组,最坏可能执行8^(x*y)次,耗时长到怀疑人生。 #include #define X 5 #define Y 5 void ShowResult(); using namespace std; int ches
hdu 1372 Knight Moves(骑士遍历/跳马问题)
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1372 题意:跳马走法,给出8*8的格子,求起点到终点的最小步数 思路:一个枝剪:马走的最大步数小于等于起终点横坐标或纵坐标相差较大的一个,,,     (其实横纵坐标间隔相加除以2即可)     玩了这么多年象棋竟然不知道。 #include using namespace std; int s
小白的数据结构与算法学习笔记(二十三)----树,森林的遍历
一、树的遍历 1、先根遍历 先访问树的根结点,然后再依次先根遍历根的每棵子树 2、后根遍历 先依次遍历每棵子树,然后再访问根结点 二、森林的遍历 1、前序遍历 按照树的先根遍历依次访问森林的每一棵树 2、后序遍历 按照树的后根遍历依次访问森林的每一棵树   三、树,森林,二叉树遍历的关系 这里的二叉树是由树或森林转换而得的二叉树。 树、森林的先根(前序)遍历与二叉树的...
骑士跳跃问题
骑士跳跃简单的说就是在8*8的国际象棋上任意位置放一个骑士(马),给出一个终点,求起点到终点的最短路径//////////这题大部人都使用回溯法,个人认为完全没有必要,使用广度搜索是最快的,不过编程实现没有采用回溯的广度搜索,而是通过穷尽进行广度搜索 ,代码量可以降低很多/////////////代码如下#include #include "memory.h" unsigned cha
骑士遍历堆栈国际象棋C++
n*n棋盘上,国际象棋走马方式,不走重复,遍历整个棋盘
骑士游历问题
导读:  本文转自http://topic.csdn.net/t/20011025/13/339519.html求解骑士游历问题       显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历,这时记住解的每一步需要记住两件事:       1.当前步的行列位置       2.当前步已经试探过哪些方向了,以便回溯回来时能够选择一个新
数据结构学习心得——二叉树的三种遍历算法
二叉树主要的遍历方式有四种,先序遍历,中序遍历,后序遍历和层次遍历(层次遍历放到下一篇博客单独讲)。 1、先序遍历 a.访问根结点 b.先序遍历左子树 c.后序遍历右子树2、中序遍历 a.先序遍历左子树 b.访问根结点 c.后序遍历右子树3、后序遍历 a.先序遍历左子树 b.后序遍历右子树 c.访问根结点看上很简单,代码实现也很简单,但是很多算法都是基于这几种遍历而衍生出来的,所
骑士巡游问题算法
骑士巡游或叫马步遍历问题描述:在n*n的棋盘上,假设一个骑士按象棋中“马”的走法,从初始坐标(x1,y1)出发,要求无重复地走遍棋盘中的每一个位置(每个点必须经过一次且只能是一次 )。请编写程序,为骑士求解巡游“路线”(或无解)。代码:#include #include using namespace std;const int n = 5; //n*n的棋盘i
74cms|骑士cms|开源招聘系统,数据结构
这个可是我花了3、4天时间,详细总结的,不知道公布出来,官方应该也不会找我吧。74cms是一个开源的招聘系统,我研究了下系统、代码,总结了下数据结构,网上应该是没有的。 觉得好的点个赞,我这几天真的挺辛苦的。。。 74cms3.7数据结构统计:     config - 系统配置         id         name - 配置项         value - 值
文章热词 数据结构 数据结构学习 数据结构课程 数据结构培训 数据结构视频教程
相关热词 c++ 数据结构与算法 第四版 c#数据结构与算法测试题 c# 数据结构和算法 python数据结构与算法教程 python数据结构教程