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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C语言-数据结构-骑士周游-马踏棋盘问题-源代码
1. 目标 对于一个指定的起始坐标,按照‘马’的走棋规则,从该坐标开始搜索一条可以覆盖棋盘每个位置的走棋路径。例如下面是从(2,0)坐标开始搜索得到的一个解。 2. 代码结构 3. 源代码 该代码仅仅是寻找到一条生路,即停止。另外对选择的起始点,和寻找下一点的顺序不同(即sposition()中case的顺序不同,对于程序执行的时间影响会很大)。 另外程序中调用了time
bfs 经典例题:骑士游历
我们先来了解一下宽度优先搜索算法:   宽度优先搜索又译为广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点...
数据结构与算法10:马踏棋盘问题(骑士周游问题)
问题描述:在一个国际象棋的棋盘上,一个马按照它的规则如何才能从一个点出发遍历每一个位置,且每个点只访问一次。     问题分析:这是一个深搜的问题,沿着一条路前进直到遍历全部的点,那就完成了整个的过程。如果不行,就回退一步,换个方向继续前进。这可以用递归很方便地实现。注意到马在某个位置最多有8个方向可以走,因此需要对这8个方向进行试探。当然这8个方向不一定都存在,比如在边缘可能就会少一些
图的周游和遍历
实验要求: 以邻接矩阵或邻接表为存储结构,建立连通无向图或有向图,并完成以下操作: (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++,用穷举法可以得到所有遍历结果
经典的骑士遍历算法,可以设置棋盘的大小,结果返回骑士的遍历路线
骑士游历算法
骑士游历,算法
C语言数据结构算法实现图的遍历
A 深度优先遍历:1.深度优先遍历的递归定义   假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通(从源点可达)的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未...
经典游戏算法之骑士走棋盘
问题描述:中国象棋中,马可以走遍棋盘上的任何角落.国际象棋中,也同样有这样的说法:骑士可以走遍棋盘上的每个格子.现在的问题是:在一个8x8的棋盘上,从任意位置开始,骑士如何可以不重复地走完所有的位置?   骑士在每一步都有8种可能的下一步走法(边界上除外),为了提高效率,可以选择所要走的下一步为下一步要选择时所能走的步数最少的一步.   函数说明: bool trav
递归——骑士巡游问题
问题 h: 【递归入门】骑士巡游问题 时间限制: 1 Sec  内存限制: 128 MB 提交: 23  解决: 14 [提交][状态][讨论版][命题人:外部导入] 题目描述 输入 n ( 1&amp;lt; = n &amp;lt; = 10 ) 代表棋盘的规模就是 n*n 的规模,骑士永远从 (1,1) 出发,要求骑士走遍所有棋盘的格子 输出 骑士的走法(遍历棋盘的所有格子)  注意方向: con...
数据结构经典算法(7)骑士走棋盘
说明:骑士旅游(Knighttour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出 已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完[所有的位 置? 解法:骑士的走法,基本上可以使用递回来解决,但是纯綷的递回在维度大时相当没有效率,  一个聪明的解法由J .C. Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路 就宽广了,骑士
骑士周游问题(暴力解决:回溯法)
建议测试数据 3 0 或 4 0
骑士游历问题
导读:  本文转自http://topic.csdn.net/t/20011025/13/339519.html求解骑士游历问题       显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历,这时记住解的每一步需要记住两件事:       1.当前步的行列位置       2.当前步已经试探过哪些方向了,以便回溯回来时能够选择一个新
每天刷个算法题20160523:骑士巡游的递归转非递归解法
为了防止思维僵化,每天刷个算法题。这里是骑士巡游的递归转非递归解法。
骑士遍历问题
问题描述:跳马问题也称骑士遍历、马踏棋盘问题:在n*n方格的棋盘上,从任意指定的方格出发,为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
马踏棋盘算法(骑士周游问题)
一、马踏棋盘算法 1、国际象棋的棋盘为8*8的方格棋盘,将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。 2、关于国际象棋“马”的走法:以“日”字为单位往斜对角上的那个方格走。如下图所示马在当前位置就有8种走法,如果不考虑边缘的特殊情况,那么需要8^64的时间复杂度才可以把整个棋盘的一个正确路径找出来。
骑士走棋盘(c/python)
骑士走棋盘:等价于中国象棋中马走日 算法思路:骑士所要走的下一步:为下一步再做选择时,选择能走的步数最少的一步。使用这个方法,在不使用递归的情况下,可以有较高的几率找出走法(有时可能也找不到走法)。C代码#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>int traval(int x, int y); int
基于Java的dfs+预见算法解决骑士游历问题
题目 骑士游历 骑士游历问题是指,在国际象棋的棋盘(8行*8列)上,一个马要遍历棋盘,即走到棋盘上的每一格,并且每隔只到达一次。设码在棋盘的某一位置(x,y)上,按照“走马日”的规则,下一步有8个方向走,如图所示。若给定起始位置(x0,y0),使用站和队列探索出一条马遍历棋盘的路径。 8 1 7 2
[算法设计与分析] 回溯法求解骑士问题/马周游问题 (C++)
实验课程:算法分析与设计 实验名称:回溯法的应用[骑士问题] (综设型实验)   第一部分 实验内容 1.实验目标 (1)熟悉使用回溯法求解问题的基本思路。 (2)掌握回溯算法的程序实现方法。 (3)理解回溯算法的特点。 2.实验任务 (1)从所给定的题目中选择一题,使用回溯法求解之。 (2)用文字来描述你的算法思路,包括解空间、限界函数、算法主要步骤等。 (3)使用C/C+...
【深度优先搜索】骑士游历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;.
POJ 1915 Knight Moves 骑士遍历问题(跳马问题)
1、对于这道题,我首先根据宽度优先搜索
算法思考--------骑士走棋盘(c语言)
一、规则说明              骑士可以从任意一个位置出发,走法和中国象棋的"马"走法类似,"走日"。问:如何走完所有的位置 二、解法          可以用递归的方法解决,但是纯粹的递归在维度大时没有效率。一个聪明的解法由J.C.Warnsdorft提出:先将最难的位置走完,接下来的路就宽广了 三、代码实现 #include int travel(int x, int
[易读易懂] 骑士游历算法 Knight's Tour Problem
1、问题描述在一个N*M的棋盘上,在任意位置放置一个骑士,骑士的走&quot;日字&quot;,和象棋中的马一样。问该骑士能否不重复遍历整个棋盘。下面的方法本质还是穷举,所以就写成可以计算出共有多少种不同的遍历方法。2、分析与思路根据题意,骑士走的下一步可能在棋盘上有多种选择(最多8种),需要选择1种,然后继续走下去,直到无处可走。无处可走时有两种情况:情况一:成功完成了遍历,那么接下来就通过回溯(回到上一步的位置,...
【数据结构和算法】全面剖析树的各类遍历方法
面试中常考到树的前序,中序,后序和层序遍历,这篇博文就带你深度剖析一下二叉树的各类遍历算法的实现二叉树的遍历主要有四种,前序、中序、后序和层序遍历的实现方式主要是:递归和非递归递归遍历的实现非常容易,非递归的实现需要用到栈,难度系数要高一点。一、二叉树节点的定义二叉树的每个节点由节点值、左子树和右子树组成。class TreeNode{ public: int val; TreeNo
HDU - 1372 骑士遍历
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...
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,...
ACM:搜索算法专题(2)——骑士问题
题目描述:     在国际象棋的棋盘上放置3个骑士的棋子,按照骑士的移动规则移动这3个棋子,使其到达同一个位置,求最少的移动次数。 解答:     本题不难。首先说明一下国际象棋的规则,棋盘由8×8=64个黑白相间的格子组成,棋子放在某一个格子中。采用二维坐标的方式表示棋盘中的每一个格子,其中水平方向从左到右用 A-H 这8个英文字母表示,竖直方向从下到上用 1-8 这8个数字表示,
hdu 1372 Knight Moves(骑士遍历/跳马问题)
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1372 题意:跳马走法,给出8*8的格子,求起点到终点的最小步数 思路:一个枝剪:马走的最大步数小于等于起终点横坐标或纵坐标相差较大的一个,,,     (其实横纵坐标间隔相加除以2即可)     玩了这么多年象棋竟然不知道。 #include using namespace std; int s
骑士遍历问题解法两中
C语言程序一种是递归算法,另一种是利用站的迭代算法
C++ 马踏棋盘(骑士周游)
马踏棋盘,用1枚马走遍棋盘。我用一个二维数组记录模拟的整个路径,x为列,y为行,以顺时针的方式寻找下一格,算法比较简单,就通过递归和循环回溯即可,就是如果是8*8的数组,最坏可能执行8^(x*y)次,耗时长到怀疑人生。 #include #define X 5 #define Y 5 void ShowResult(); using namespace std; int ches
骑士遍历
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...
数据结构算法题/树的遍历(深度优先和广度优先)
在编程生活中,我们总会遇见树性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及过程。现在假设有一颗这样树,(是不是二叉树都没关系,原理都是一样的)。此外二叉树可以递归的方法遍历。   1、深度优先 英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。对于上面的例子来说深度优先遍历的结果...
数据结构与算法--图的遍历
图的遍历:深度优先、广度优先 遍历     图的遍历是指从图中的某一顶点出发,按照一定的策略访问图中的每一个顶点。当然,每个顶点有且只能被访问一次。     在图的遍历中,深度优先和广度优先是最常使用的两种遍历方式。这两种遍历方式对无向图和有向图都是适用的,并且都是从指定的顶点开始遍历的。先看下两种遍历方式的遍历规则: 深度优先     深度优先遍历也
【DFS】(一)最简单的递归dfs——水坑问题(poj2386)
简单
【数据结构】中树的三种遍历方式详解
【数据结构】中树的三种遍历方式详解
数据结构作业——————二叉树的三种遍历方式
数据结构作业: 二叉树的建立 三种遍历方式 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...
用java写的马踏棋盘算法
将马随机放在国际象棋的8×8棋盘Board[0~7][0~7]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。
poj2488--骑士遍历棋盘
题目大意: 就是给一个 p*q的棋盘,一个骑士从任意位置出发,要求遍历棋盘所有的位置(骑士按‘日’字走)。 思路: 把A1这个位置当做起点,然后按字母表方向(题目要求)搜索,如果位置可以走则再从新位置往下走(其实就是深度搜索)。 注意每种情况输出完以后还要输出一个空格。 #include&amp;lt;iostream&amp;gt; using namespace std; #define le...
二叉树的遍历(C语言)(数据结构)
二叉树的基本操作  按前辈们的说法,在嵌入式的开发中并不用得到二叉树。在次就仅仅对二叉树的基本操作作简单介绍。 二叉树性质  (1)第 i 层最多有 2^(i-1) 个节点。 (2)深度为 k 的二叉树至多有 2^k - 1 个节点。 (3)若一个二叉树终端节点个数为 n,度为 2 的节点个数为 m,则有 n = m+1。 (4)有 n 个节点的完全二叉树深度为 log2(n) + 1...
数据结构之"二叉树的三种遍历方法"
1、什么是二叉树 定义:有且仅有一个根节点,每个节点只有一个父节点,最多含有两个子节点,子节点有左右之分。 2、二叉树的遍历 二叉树是一种树形结构,遍历就是要让树中的节点被且仅被访问一次,即按一定规律排列成一个线性队列。二叉树是一种递归定义的结构,包含三个部分:根节点(N)、左子树(L)、右子树(R)。根据这三个部分的访问次序对二叉树的遍历进行分类,总共有6种遍历方案:NLR、NRL 、LN...
骑士巡游问题算法
骑士巡游或叫马步遍历问题描述:在n*n的棋盘上,假设一个骑士按象棋中“马”的走法,从初始坐标(x1,y1)出发,要求无重复地走遍棋盘中的每一个位置(每个点必须经过一次且只能是一次 )。请编写程序,为骑士求解巡游“路线”(或无解)。代码:#include #include using namespace std;const int n = 5; //n*n的棋盘i
文章热词 决策树算法评价标准熵 计算机导论培训 CAVLC系数矩阵解析 设计制作学习 统计学稳健估计opencv函数
相关热词 ios获取idfa server的安全控制模型是什么 sql android title搜索 python数据结构与算法教程 python教程骑马与砍杀