数据结构与算法之骑士遍历 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个回答

3
u012734723
bluesnail95 谢谢分享
接近 2 年之前 回复

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

1
qq_27718453
庄粟 死循环了-_-!
接近 2 年之前 回复
u012734723
bluesnail95 当我从(0,0)开始遍历的时候是可以找到解的,但是进入了while循环几百万次,怎么会进入这么多,
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
图的周游和遍历
实验要求: 以邻接矩阵或邻接表为存储结构,建立连通无向图或有向图,并完成以下操作: (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...
bfs 经典例题:骑士游历
我们先来了解一下宽度优先搜索算法:   宽度优先搜索又译为广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点...
骑士游历算法
骑士游历,算法
骑士游历问题【JAVA板】代码详细流
先说明一下算法问题,在棋盘上,要怎么选择行走的方向才能遍历整个棋盘呢。简单来说,就是选择一个在选择了它之后它的下一步可选方向最少的那一个方向。总体上就是先选择比较困难的路来走,将比较简单的路线留到后面再走。 那么接下来我们先来看看一个8x8的棋盘上每个格子的可走方向来理解一下这个算法。 先上代码。(注意!下面这个代码不是用来解决骑士游历问题的) `public class Bushu { pr...
骑士遍历-c++,用穷举法可以得到所有遍历结果
经典的骑士遍历算法,可以设置棋盘的大小,结果返回骑士的遍历路线
基于Java的dfs+预见算法解决骑士游历问题
题目 骑士游历 骑士游历问题是指,在国际象棋的棋盘(8行*8列)上,一个马要遍历棋盘,即走到棋盘上的每一格,并且每隔只到达一次。设码在棋盘的某一位置(x,y)上,按照“走马日”的规则,下一步有8个方向走,如图所示。若给定起始位置(x0,y0),使用站和队列探索出一条马遍历棋盘的路径。 8 1 7 2
C语言-数据结构-骑士周游-马踏棋盘问题-源代码
1. 目标 对于一个指定的起始坐标,按照‘马’的走棋规则,从该坐标开始搜索一条可以覆盖棋盘每个位置的走棋路径。例如下面是从(2,0)坐标开始搜索得到的一个解。 2. 代码结构 3. 源代码 该代码仅仅是寻找到一条生路,即停止。另外对选择的起始点,和寻找下一点的顺序不同(即sposition()中case的顺序不同,对于程序执行的时间影响会很大)。 另外程序中调用了time
每天刷个算法题20160523:骑士巡游的递归转非递归解法
为了防止思维僵化,每天刷个算法题。这里是骑士巡游的递归转非递归解法。
C语言数据结构算法实现图的遍历
A 深度优先遍历:1.深度优先遍历的递归定义   假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通(从源点可达)的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未...
Knight Tour 骑士走棋盘算法(附代码)
骑士的走法为国际象棋的走法,骑士可以由任何一个位置出发,要求走完所有的位置。 基本情况下是可以使用递归,但是在递归维度大的时候,时间复杂度很高,效率很低。 下面介绍一个聪明的解法: 先将所在位置的周围八个方向是否可走记录下来,如果可走方向为0,则无解;如果可走方向为1,则直接走出路最少的方向;如果可走的方向大于1,再找出下一个位置的出路数,同样的寻找可走方向,然后走可走方向中
骑士巡游问题算法
骑士巡游或叫马步遍历问题描述:在n*n的棋盘上,假设一个骑士按象棋中“马”的走法,从初始坐标(x1,y1)出发,要求无重复地走遍棋盘中的每一个位置(每个点必须经过一次且只能是一次 )。请编写程序,为骑士求解巡游“路线”(或无解)。代码:#include #include using namespace std;const int n = 5; //n*n的棋盘i
递归算法实现骑士遍历棋盘问题
用递归算法是实现骑士遍历棋盘问题!!c++语言实现
经典游戏算法之骑士走棋盘
问题描述:中国象棋中,马可以走遍棋盘上的任何角落.国际象棋中,也同样有这样的说法:骑士可以走遍棋盘上的每个格子.现在的问题是:在一个8x8的棋盘上,从任意位置开始,骑士如何可以不重复地走完所有的位置?   骑士在每一步都有8种可能的下一步走法(边界上除外),为了提高效率,可以选择所要走的下一步为下一步要选择时所能走的步数最少的一步.   函数说明: bool trav
马踏棋盘算法(骑士周游问题)
一、马踏棋盘算法 1、国际象棋的棋盘为8*8的方格棋盘,将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。 2、关于国际象棋“马”的走法:以“日”字为单位往斜对角上的那个方格走。如下图所示马在当前位置就有8种走法,如果不考虑边缘的特殊情况,那么需要8^64的时间复杂度才可以把整个棋盘的一个正确路径找出来。
马踏棋盘算法 [骑士周游问题] --->图
马塔棋盘算法又称骑士周游或骑士漫游问题是算法设计的经典问题之一。 国际象棋的棋盘为8*8的方格棋盘,现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动,要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。编写代码,实现马踏棋盘的操作,要求用1-64 来标注“马”移的路径。 关于马的走法: 马踏棋盘的一个解 对于在n*n的棋盘上,档n>=5且为偶数的时候,
递归——骑士巡游问题
问题 h: 【递归入门】骑士巡游问题 时间限制: 1 Sec  内存限制: 128 MB 提交: 23  解决: 14 [提交][状态][讨论版][命题人:外部导入] 题目描述 输入 n ( 1&amp;lt; = n &amp;lt; = 10 ) 代表棋盘的规模就是 n*n 的规模,骑士永远从 (1,1) 出发,要求骑士走遍所有棋盘的格子 输出 骑士的走法(遍历棋盘的所有格子)  注意方向: con...
[易读易懂] 骑士游历算法 Knight's Tour Problem
1、问题描述在一个N*M的棋盘上,在任意位置放置一个骑士,骑士的走&quot;日字&quot;,和象棋中的马一样。问该骑士能否不重复遍历整个棋盘。下面的方法本质还是穷举,所以就写成可以计算出共有多少种不同的遍历方法。2、分析与思路根据题意,骑士走的下一步可能在棋盘上有多种选择(最多8种),需要选择1种,然后继续走下去,直到无处可走。无处可走时有两种情况:情况一:成功完成了遍历,那么接下来就通过回溯(回到上一步的位置,...
骑士遍历
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...
骑士走棋盘(c/python)
骑士走棋盘:等价于中国象棋中马走日 算法思路:骑士所要走的下一步:为下一步再做选择时,选择能走的步数最少的一步。使用这个方法,在不使用递归的情况下,可以有较高的几率找出走法(有时可能也找不到走法)。C代码#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>int traval(int x, int y); int
马踏棋盘问题(骑士周游问题)及其优化算法java实现
马踏棋盘问题java实现(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用或者进一步理解为一颗8叉树的深度遍历package ccnu.offer.tree; import java.awt.Point; import java.util.ArrayList; import java.util.Scanner; public class Demo07 { private static ...
骑士游历【codevs】【黄金题】【棋盘型动态规划】
骑士游历 历经千难万险,最终的ac程序让我给凑出来了。 关于我的不细心的点在于1、忘记了日字行走是怎么走了,一开始只想到了两种走法。2、没有去计算数据范围。 #include&amp;lt;iostream&amp;gt; #include&amp;lt;cstring&amp;gt; #include&amp;lt;queue&amp;gt; using namespace std; #define ll long long int ...
数据结构——栈——迷宫(c++)
迷宫旅行游戏   项目简介 迷宫只有两个门,一个门叫入口,另一个门叫出口。一个骑士骑马从入口走进迷宫,迷宫中设置很多墙壁,对前进方向形成了多处障碍。骑士需要在迷宫中寻找通路以到达出口。   设计思路 迷宫问题的求解过程可以采用回溯法即在一定的约束条件下试探地搜索前进,若前进中受阻,则及时回头纠正错误另择通路继续搜索的方法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可达
算法思考--------骑士走棋盘(c语言)
一、规则说明              骑士可以从任意一个位置出发,走法和中国象棋的"马"走法类似,"走日"。问:如何走完所有的位置 二、解法          可以用递归的方法解决,但是纯粹的递归在维度大时没有效率。一个聪明的解法由J.C.Warnsdorft提出:先将最难的位置走完,接下来的路就宽广了 三、代码实现 #include int travel(int x, int
【数据结构和算法】全面剖析树的各类遍历方法
面试中常考到树的前序,中序,后序和层序遍历,这篇博文就带你深度剖析一下二叉树的各类遍历算法的实现二叉树的遍历主要有四种,前序、中序、后序和层序遍历的实现方式主要是:递归和非递归递归遍历的实现非常容易,非递归的实现需要用到栈,难度系数要高一点。一、二叉树节点的定义二叉树的每个节点由节点值、左子树和右子树组成。class TreeNode{ public: int val; TreeNo
[算法设计与分析] 回溯法求解骑士问题/马周游问题 (C++)
实验课程:算法分析与设计 实验名称:回溯法的应用[骑士问题] (综设型实验)   第一部分 实验内容 1.实验目标 (1)熟悉使用回溯法求解问题的基本思路。 (2)掌握回溯算法的程序实现方法。 (3)理解回溯算法的特点。 2.实验任务 (1)从所给定的题目中选择一题,使用回溯法求解之。 (2)用文字来描述你的算法思路,包括解空间、限界函数、算法主要步骤等。 (3)使用C/C+...
一道搜索好题
给定一个数S,找任意个正整数a1,a2,…,an,使得它们的和恰好等于S,且它们的倒数之和与1的差不超过10^-6。 输出任意一种方案或者输出无解。 S<=65536 解析: 事实上也是简单的搜索。 从小到大枚举每个数,加入试试看。 两个剪枝: ①当前的和加上最大的和到不了1,退出。//这个剪枝怎么写啊 ②当前的和加上最小的和都超过了1,退出。 代码:#include<iostre
数据结构算法题/树的遍历(深度优先和广度优先)
在编程生活中,我们总会遇见树性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及过程。现在假设有一颗这样树,(是不是二叉树都没关系,原理都是一样的)。此外二叉树可以递归的方法遍历。   1、深度优先 英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。对于上面的例子来说深度优先遍历的结果...
数据结构作业——————二叉树的三种遍历方式
数据结构作业: 二叉树的建立 三种遍历方式 L:遍历左子树 D:访问根节点 R:遍历右子树 DLR:先序遍历 LDR:中序遍历 LRD:后序遍历 #include&amp;amp;amp;lt;bits/stdc++.h&amp;amp;amp;gt; using namespace std; typedef char ElemType; struct node{ ElemType data; nod...
C/C++实现数据结构之图的遍历算法
图形结构是一种在生活以及工业中很常用的数据结构。有着关系明确、运算快捷的优点。但是学习难、入门起点高,对数学能力有很高的要求。 图的遍历 图的遍历和树的遍历类似。首先这里就不再赘述图的逻辑结构了。有向图和无向图这里就先假设为邻接矩阵表示,直观的体现下图的存储结构的特点。邻接表不过就是有入边和出边来体现图的点集和边集的特点。这两种逻辑结构其实并没有太大的区别。 就像树有三种遍历方式一样(前序遍历、中...
骑士巡游问题(马步问题),用回溯法实现的
【问题描述】 骑士巡游问题:从国际象棋棋盘上任意给定的方格开始移动骑士,相继地到达所有的64个方格,进入每个方格一次且仅进入一次。
zufeoj_骑士巡游问题
题目链接:http://acm.ocrosoft.com/problem.php?cid=1222&amp;amp;pid=33题目描述输入 n ( 1&amp;lt; = n &amp;lt; = 10 ) 代表棋盘的规模就是 n*n 的规模,骑士永远从 (1,1) 出发,要求骑士走遍所有棋盘的格子输出 骑士的走法(遍历棋盘的所有格子) 注意方向:const int dx[8]={ -2,-2, -1, 1,2, 2,...
数据结构与算法--图的遍历
图的遍历:深度优先、广度优先 遍历     图的遍历是指从图中的某一顶点出发,按照一定的策略访问图中的每一个顶点。当然,每个顶点有且只能被访问一次。     在图的遍历中,深度优先和广度优先是最常使用的两种遍历方式。这两种遍历方式对无向图和有向图都是适用的,并且都是从指定的顶点开始遍历的。先看下两种遍历方式的遍历规则: 深度优先     深度优先遍历也
数据结构之"二叉树的三种遍历方法"
1、什么是二叉树 定义:有且仅有一个根节点,每个节点只有一个父节点,最多含有两个子节点,子节点有左右之分。 2、二叉树的遍历 二叉树是一种树形结构,遍历就是要让树中的节点被且仅被访问一次,即按一定规律排列成一个线性队列。二叉树是一种递归定义的结构,包含三个部分:根节点(N)、左子树(L)、右子树(R)。根据这三个部分的访问次序对二叉树的遍历进行分类,总共有6种遍历方案:NLR、NRL 、LN...
骑士游历问题——至少需要多少步
水水的chessboard 题目描述 国际象棋的棋盘大家应该都很熟悉了,那么给定棋盘上的两个格位,一个骑士(knight)需要几步才能从其中一个格位来到另一个格位呢? //注意骑士沿一个3*2方格区域的对角线移动。 输入 多组测试数据。对于每组数据,包含两个输入数据,分别为国际象棋棋盘上两个格位的位置。 输出 对于每组数据,输出一行It takes (ans) steps to get ...
马踏棋盘算法(骑士周游算法)
将马按照走步规则,走遍8*8棋盘。 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;time.h&amp;gt; #define X 8 #define Y 8 int chess[X][Y]; //找到基于(x,y)位置的下一个可走的位置 int nextxy(int *x,int *y,int count) { switch(count) { ...
骑士遍历堆栈国际象棋C++
n*n棋盘上,国际象棋走马方式,不走重复,遍历整个棋盘
【数据结构】中树的三种遍历方式详解
【数据结构】中树的三种遍历方式详解
数据结构(C++)——图的遍历算法:广度优先搜索、深度优先搜索、优先级搜索算法
图的遍历算法 图的遍历都可以理解为,将非线性结构转化为半线性结构的过程。经遍历而确定的边类型中,最重要的一类即所谓的树边,它们与所有顶点共同构成了原图的一棵支撑树(森林),称作遍历树(traversal tree)。     广度优先搜索(BFS) 广度优先搜索(breadth-first search, BFS)采用的策略,可概括为:     越早被访问到的定点,其邻居越优先被选用 ...
数据结构与算法18-图的遍历
从图中某一个顶点出发访遍图中其余顶点,且使每个顶点权被访问一次,这一过程就叫做图的遍历(Traversing   Graph)。   深度优先遍历(Depth_First_Search) 从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径想通的顶点都被访问到。 事实上,我们这里讲到的是连通图,对于非连通图,只需要对它的连通分量分别进行深度...
【数据结构】二叉树的遍历及应用
  【fishing-pan:https://blog.csdn.net/u013921430转载请注明出处】 前言       在二叉树的应用中,常常要求在树中查找某些结点,或者对树中的结点统一进行某种处理。因此,就提到了二叉树的遍历问题,对于线性结构来说,遍历是一个很容易解决的问题,而二叉树偏偏是一种非线性的结构,因此需要寻找一种规律。        二叉树由三个基本单元组成,分别是根...
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 python数据结构与算法教程 nlp视频算法音频算法