栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构(Java)马踏棋盘算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构(Java)马踏棋盘算法

一、游戏介绍 1) 马踏棋盘算法也被称为骑士周游问题 2) 将马随机放在国际象棋的 8×8 棋盘 Board[0 ~ 7][0 ~ 7] 的某个方格中,马按走棋规则 ( 马走日字 ) 进行移动。要求每个方格只进入一次,走遍棋盘上全部 64 个方格

 二、代码思路

        骑士周游问题的解决步骤和思路:

1.  创建棋盘 chessBoard , 是一个二维数组

2.  将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList), 最多有8个位置, 每走一步,就使用step+1

3. 遍历ArrayList中存放的所有位置,看看哪个可以走通 , 如果走通,就继续,走不通,就回溯.

4.  判断马儿是否完成了任务,使用   step 和应该走的步数比较 , 如果没有达到数量,则表示没有完成任务,将整个棋盘置0

        程序应由包含以下几部分:

1.计算下一步棋怎么走

2.只要当前棋子有路可走,就递归地走

3.(优化)对某个棋子每个可走的位置(比如上图的 0~7)接下来可走的位置进行比较(下下一步),选择下下一步可走位置最少的位置作为本次移动的位置(贪心算法的思想,尽可能少走冤枉路)

三、代码实现
class horseChess {
    public static int X = 6, Y = 6;
    public static int[][] chessBoard = new int[X][Y];//棋盘
    public static int[][] isVisited = new int[X][Y];
    public static Boolean flag = false;

    //马踏棋盘的遍历过程
    public static void traversal(Point point, int step) {
        if (flag) return;
        isVisited[point.x][point.y] = 1;
        chessBoard[point.x][point.y] = step;
        ArrayList points = nextPosition(point);
        points.sort(new Comparator() {
            @Override
            public int compare(Point o1, Point o2) {
                int count1 = nextPosition(o1).size();
                int count2 = nextPosition(o2).size();
                if (count1 < count2) return -1;
                else if (count1 == count2) return 0;
                else return 1;
            }
        });
        while (!points.isEmpty()) {
            //对point集合进行排序,如果一个点的下一步可走位置较少,就给它较高的优先级。使用贪心的思想
            Point p = points.remove(0);
            if (isVisited[p.x][p.y] == 0) traversal(p, step + 1);
        }
        if (step < X * Y && !flag) {
            chessBoard[point.x][point.y] = 0;
            isVisited[point.x][point.y] = 0;
        } else flag = true;
    }

    //计算当前棋子下一步可以走哪些位置
    public static ArrayList nextPosition(Point curPoint) {
        ArrayList points = new ArrayList<>();
        if (curPoint.x + 1 < X && curPoint.y + 2 < Y) points.add(new Point(curPoint.x + 1, curPoint.y + 2));
        if (curPoint.x + 2 < X && curPoint.y + 1 < Y) points.add(new Point(curPoint.x + 2, curPoint.y + 1));
        if (curPoint.x + 2 < X && curPoint.y - 1 >= 0) points.add(new Point(curPoint.x + 2, curPoint.y - 1));
        if (curPoint.x + 1 < X && curPoint.y - 2 >= 0) points.add(new Point(curPoint.x + 1, curPoint.y - 2));
        if (curPoint.x - 1 >= 0 && curPoint.y - 2 >= 0) points.add(new Point(curPoint.x - 1, curPoint.y - 2));
        if (curPoint.x - 2 >= 0 && curPoint.y - 1 >=0) points.add(new Point(curPoint.x - 2, curPoint.y - 1));
        if (curPoint.x - 2 >= 0 && curPoint.y + 1 < Y) points.add(new Point(curPoint.x - 2, curPoint.y + 1));
        if (curPoint.x - 1 >= 0  && curPoint.y + 2 < Y) points.add(new Point(curPoint.x - 1, curPoint.y + 2));
        return points;
    }

}

测试:

 @Test
    public void testTraversal() {
        horseChess.traversal(new Point(1, 3), 1);
        for (int i = 0; i < horseChess.X; i++) {
            for (int j = 0; j < horseChess.Y; j++) {
                System.out.print(String.format("%2d",horseChess.chessBoard[i][j]) + " ");
            }
            System.out.println();

        }
    }



结果(数字表示走了多少步来到了该位置,初试位置为 1 ):

21  8 11 32 25  2 
10 31 22  1 12 33 
 7 20  9 26  3 24 
30 17 28 23 34 13 
19  6 15 36 27  4 
16 29 18  5 14 35 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950849.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号