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

马踏棋盘(java)

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

马踏棋盘(java)

这个是我的算法课程的期末大作业

我是参考了网课老师讲的骑士回游法写的

花了一天半写的,感觉有些冗余,到时候再改一下

代码

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

import static java.lang.System.exit;



public class horse {

    private static Scanner scanner = new Scanner(System.in);

    private static int X; // 初始化棋盘的列数为8
    private static int Y; // 初始化棋盘的行数为8
    private static boolean visited[];//创建一个数组,标记棋盘的各个位置是否被访问过
    //使用一个属性,标记是否棋盘的所有位置都被访问
    private static boolean finished; // 如果为true,表示成功
    private static int chessMap[][] ;//棋盘数组
    private static int step;//步数
    private static int size;//棋盘的尺寸
    private static int change;//控制检查位置合不合法
    private static ArrayList workedPoints = new ArrayList<>();//记录所有走过的点
    private static int row;//马儿起始的行
    private static int column;//马儿起始的列

    public static void main(String[] args) {

        int choice;//主菜单选择
        boolean start = true;//游戏是否退出的控件
        row = 6;//马儿起始的行
        column = 1;//马儿起始的列

        Point point = new Point(column - 1, row - 1);//马儿起始点
        ArrayList pointList = new ArrayList<>();//存储可以动的点

        while(start){

            flushTage();//刷新游戏界面
            System.out.println("===================马踏棋盘游戏===================");
            System.out.println("|请选择:ttttttttt   |");
            System.out.println("|ttttt1.开始游戏tttt   |");//进去选择你所需要创建的地图
            System.out.println("|ttttt2.查看答案tttt   |");//多种不同的答案
            System.out.println("|ttttt3. 退 出 tttt   |");
            System.out.println("================================================");
            System.out.print("请输入相应数字执行其功能:");
            choice = scanner.nextInt();

            switch (choice){

                case 1:
                    //开始游戏
                    step = 1;//初始化步数为1
                    System.out.print("请输入棋盘的尺寸(大于2的整数):");
                    size = scanner.nextInt();//输入棋盘的尺寸
                    System.out.print("请输入马儿的起始行和列:");
                    column = scanner.nextInt();
                    row = scanner.nextInt();
                    point = new Point(column - 1, row - 1);//马儿起始点
                    pointList = new ArrayList<>();//存储可以动的点
                    X = size;
                    Y = size;
                    chessMap = new int[size][size];
                    if(chessBoard(size)){//判断棋盘的大小是否合法
                        ArrayList next = next(point);//显示可走的点
                        paintChess(workedPoints, point, next, step);
                    }
                    break;

                case 2:
                    System.out.print("请输入棋盘的尺寸(大于2的整数):");
                    size = scanner.nextInt();//输入棋盘的尺寸
                    step = 1;//初始化步数为1
                    X = size;
                    Y = size;
                    System.out.print("请输入马儿的起始行和列:");
                    row = scanner.nextInt();
                    column = scanner.nextInt();
                    chessMap = new int[size][size];
                    visited = new boolean[size * size];
                    //测试一下耗时
                    long startT = System.currentTimeMillis();
                    if(chessBoard(size)){//判断棋盘的大小是否合法
                        travelChessBoard(chessMap, row-1, column-1, step);
                        //输出棋盘的最后情况
                        for(int[] rows : chessMap) {
                            for(int step: rows) {
                                System.out.print(step + "t");
                            }
                            System.out.println();
                        }
                    }
                    long endT = System.currentTimeMillis();
                    System.out.println("共耗时: " + (endT - startT) + " 毫秒");
                    break;

                case 3:
                    start = false;
                    flushTage();//刷新页面
                    System.out.println("===================马踏棋盘游戏===================");
                    System.out.println("|ttttttttttt   |");
                    System.out.println("|ttttt退出成功 tttt   |");
                    System.out.println("|ttttttttttt   |");
                    System.out.println("================================================");
                    break;

                default:
                    System.out.println("输入的数字不合法,请重新输入");
                    break;
            }
        }
        //选择地图大小
        //目前所在的位置为马头♞
        //游戏页面出现可选择的位置,使用★号标志
        //去过的位置标志为相应的步数,黑白格子分明
        //走过的步数也显示出来
    }

    //游戏界面刷新
    public static void flushTage(){
        for (int i = 0; i < 5; i++){
            System.out.println();
        }
    }

    //判断棋盘大小是否合法
    public static boolean chessBoard(int size){
        Scanner scanner = new Scanner(System.in);
        while (size < 3){//判断棋盘尺寸是否合法
            System.out.print("请输入棋盘的尺寸(大于2的整数):");
            size = scanner.nextInt();
        }
        return true;
    }

    
    public static void paintChess(ArrayList workedPoints, Point point, ArrayList pointList, int step) {

        flushTage();

        int chessMap[][] = new int[X][Y];//每次进入该方法都会新建一个空白地图

        chessMap[point.x][point.y] = 2;//马儿目前所在位置♞

        int m = chessMap[0].length * chessMap[0].length + 10;//设置一个特定的数值代表可以移动的位置

        for (int i = 0; i < pointList.size(); i++) {
            int x = (int) pointList.get(i).getX();
            int y = (int) pointList.get(i).getY();
            chessMap[x][y] = m;//设置特殊字作为可移动点☆
        }

        for (int i = 0; i < workedPoints.size(); i++) {
            int x = (int) workedPoints.get(i).getX();
            int y = (int) workedPoints.get(i).getY();
            chessMap[x][y] = 1;//设置1为走过的点■
        }

        if (change == 1){
            chessMap[point.x][point.y] = 2;//马儿目前所在位置♞
        }

        System.out.println("===================马踏棋盘游戏===================");
        System.out.print("tttt ");
        for (int i = 0; i < size; i++){
            System.out.print((i+1)+" ");
        }
        System.out.println();
        paintmap1(chessMap, m);
        System.out.println("                 【step = " + step+"】");
        System.out.println("================================================");
            workedPoints.add(new Point(point));//添加新选中的位置作为已走过的点
            int xi = X + 10;//取特殊点,防止取中与列相同的数字
            int xj = X + 12;//取特殊点,防止取中与列相同的数字
            System.out.println("【退回上一步请输入:"+xi+" "+xi+"】");
            System.out.println("【退出游戏请输入:"+xj+" "+xj+"】");
            System.out.print("请选择你所需要走的点(如3行2列,则输入3 2):");

            int a = scanner.nextInt();//行数
            int b = scanner.nextInt();//列数
            //一系列撤回
            change = 0;//作为检查位置合不合法的控制
            //马头没回去
            if (a == xi && b == xi){
                //在集合里面所有的点都是有顺序的
                int len = workedPoints.size();//获取长度
                workedPoints.remove(len-1);//删除最后一个走过的点
                //回到上一个点
                Point point1 = workedPoints.get(len - 2);
                a = point1.x + 1;
                b = point1.y + 1;
                step = step - 2;
                change = 1;//当chang=1时,不检查位置合不合法
                workedPoints.remove(workedPoints.size()-1);
            }else if (a == xj && b == xj){
                flushTage();//刷新页面
                System.out.println("===================马踏棋盘游戏===================");
                System.out.println("|ttttttttttt   |");
                System.out.println("|ttttt游戏失败 tttt   |");
                System.out.println("|ttttttttttt   |");
                System.out.println("|tt【1】继续游戏ttt【2】结束游戏tt   |");
                System.out.println("================================================");
                System.out.print("请输入相应数字执行其功能:");
                int choice = scanner.nextInt();
                if (choice == 2){
                    exit(0);
                }
                else if (choice == 1){
                    return;
                }else {
                    while (choice != 1 || choice != 2){
                        System.out.print("请输入【1~2】之间的数字:");
                        choice = scanner.nextInt();
                        if (choice == 2){
                            exit(0);
                        }
                        else if (choice == 1){
                            return;
                        }
                    }
                }
            }
            Point cp = new Point(a-1, b-1);
            //做出判断,不能选择其他地方的,只能选择星星的
            //且不能走回走过的点
            //有冗余
            while(true){
                if (change==1)break;
                if (pointList.contains(cp)){
                    if(workedPoints.contains(cp)){
                        System.out.print("输入的位置不合法,请重新输入:");
                        a = scanner.nextInt();//行数
                        b = scanner.nextInt();//列数
                        cp = new Point(a-1, b-1);
                    }else break;
                }
                else {
                    System.out.print("输入的位置不合法,请重新输入:");
                    a = scanner.nextInt();//行数
                    b = scanner.nextInt();//列数
                    cp = new Point(a-1, b-1);
                }
            }
            //下一个可移动的所有点
            ArrayList nextPoints = next(cp);//不报结束是因为还有重复的点可移动,却没有去除

            for (Point p : workedPoints){
                if (nextPoints.contains(p)){
                    nextPoints.remove(p);
                }
            }
            //下一步的点的集合为0,有两种情况
            //1、step == X * Y ----> 胜利
            //2、step < X * Y  ----> 失败
            step++;
            if(nextPoints.size() == 0){
                if (step == X * Y)
                    winGame();//游戏胜利

                else failGame();//游戏失败
            }//workedPoints可能还需要再删除多一个,因为它包含了cp
            paintChess(workedPoints, cp, nextPoints, step);
        }

    
    public static ArrayList next(Point curPoint){
        ArrayList ps = new ArrayList<>();//存储可移动的位置

        Point point = new Point();
        //找出可以移动的点,八个位置挨个判断
        if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y - 1) >= 0){
            ps.add(new Point(point));
        }
        if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y + 1) < Y){
            ps.add(new Point(point));
        }

        if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y - 1) >= 0){
            ps.add(new Point(point));
        }
        if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y + 1) < Y){
            ps.add(new Point(point));
        }

        if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y - 2) >= 0){
            ps.add(new Point(point));
        }
        if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y - 2) >= 0){
            ps.add(new Point(point));
        }

        if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y + 2) < Y){
            ps.add(new Point(point));
        }
        if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y + 2) < Y){
            ps.add(new Point(point));
        }

        return ps;
    }

    //游戏失败
    public static void failGame(){
        flushTage();//刷新页面
        System.out.println("===================马踏棋盘游戏===================");
        System.out.println("|ttttttttttt   |");
        System.out.println("|ttttt游戏失败 tttt   |");
        System.out.println("|ttttttttttt   |");
        System.out.println("|tt【1】继续游戏ttt【2】结束游戏tt   |");
        System.out.println("================================================");
        System.out.print("请输入相应数字执行其功能:");
        int choice = scanner.nextInt();
        if (choice == 2){
            exit(0);
        }
        else if (choice == 1){
            return;
        }else {
            while (choice != 1 || choice != 2){
                    System.out.print("请输入【1~2】之间的数字:");
                    choice = scanner.nextInt();
                if (choice == 2){
                    exit(0);
                }
                else if (choice == 1){
                    return;
                }
            }
        }
    }

    //游戏胜利
    public static void winGame(){
        flushTage();//刷新页面
        System.out.println("===================马踏棋盘游戏===================");
        System.out.println("|ttttttttttt   |");
        System.out.println("|ttttt游戏胜利 tttt   |");
        System.out.println("|ttttttttttt   |");
        System.out.println("|tt【1】继续游戏ttt【2】结束游戏tt   |");
        System.out.println("================================================");
        System.out.print("请输入相应数字执行其功能:");
        int choice = scanner.nextInt();
        if (choice == 2){
            exit(0);
        }
        else if (choice == 1){
            return;
        }else {
            while (choice != 1 || choice != 2){
                System.out.print("请输入【1~2】之间的数字:");
                choice = scanner.nextInt();
                if (choice == 2){
                    exit(0);
                }
                else if (choice == 1){
                    return;
                }
            }
        }
    }

    //绘制动态地图
    public static void paintmap1(int[][]chessMap, int m){
        for (int i = 0; i < chessMap.length; i++) {
            System.out.print("tttt"+(i+1));
            for (int j = 0; j < chessMap[i].length; j++) {

                if (chessMap[i][j] == 2) {
                    System.out.print("♞");//表示走过的点
                }

                if (chessMap[i][j] == 1) {
                    System.out.print("■");//表示走过的点
                }

                if (chessMap[i][j] == 0) {
                    System.out.print("□");//表示未走过的点
                }//添加==1为黑猩猩,表示走过的点

                if (chessMap[i][j] == m) {
                    System.out.print("☆");//表示可选择的点
                }

            }
            System.out.println();
        }
    }

    
    public static void travelChessBoard(int [][] chessMap, int row, int column, int step){
        chessMap[row][column] = step;
        visited[row * X +column] = true;//表示位置已被访问过
        ArrayList ps = next(new Point(column, row));//获取当前位置可以走的下一个位置的集合
        sort(ps);
        //遍历 ps
        while (!ps.isEmpty()){
            Point p = ps.remove(0);
            //判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {//说明还没有访问过
                travelChessBoard(chessMap, p.y, p.x, step + 1);
            }
        }
        //判断马儿是否完成了任务,使用   step 和应该走的步数比较 ,
        //如果没有达到数量,则表示没有完成任务,将整个棋盘置0
        //说明: step < X * Y  成立的情况有两种
        //1. 棋盘到目前位置,仍然没有走完
        //2. 棋盘处于一个回溯过程
        if (step < X * Y && !finished){
            chessMap[row][column] = 0;
            visited[row * X + column] = false;
        }else {
            finished = true;
        }
    }

    //根据当前这个一步的所有的下一步的选择位置,进行非递减排序, 减少回溯的次数
    public static void sort(ArrayList ps){
        ps.sort(new Comparator() {
            @Override
            public int compare(Point o1, Point o2) {
                //获取o1的下一步的所有位置个数
                int count1 = next(o1).size();
                //获取o2的下一步的所有位置的个数
                int count2 = next(o2).size();
                if (count1 < count2){
                    return -1;
                }else if (count1 == count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}

实现图

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

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

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