Java经典谜题puzzle类迷宫实现

Puzzle项目实现设计

项目介绍：

该项目类似于迷宫项目实现。采用栈对puzzle中，从头走到尾巴的行走路径进行打印。

项目功能：

初始正方形中的带圆圈的数字是可以移动到沿着行的其他正方形的标记。

项目所用知识点：

使用Java面向对象思想，用递归 或 栈或者队列实现编程。

项目实现思路：

在拼图的每个步骤，可以移动标记的正方形中由当前占据的整数指示的方格数。 标记可以沿着该行向左或向右移动，但可以不移动经过任一端。 例如，唯一合法的第一步是将标记向右移动三个方格，因为没有空间向左移动三个空格。

如果圆圈能够移动到最后0的位置，返回true，否则返回false。如何检测不能解决的结构，是否存在可以改善执行时间的方法。程序运行，然后打印出方格，再打印详细的移动路径。下图示例演示跳转过程：一维数组4 8 5 2 3 5 1 6 4 0

项目实现：

puzzle类

import java.util.Scanner;

public class Puzzle {
    private int puzzleLong;
    private PuzzleValue[] puzzleValue;
    public void invalue(){
        System.out.println("输入puzzle的长度");
        Scanner scanner=new Scanner(System.in);
        puzzleLong=scanner.nextInt();
        puzzleValue=new PuzzleValue[puzzleLong];//创建一个PuzzleValue型的一维数组长度为puzzlelong
        System.out.println("请输入puzzle的数值");
        for(int i=0;i<puzzleLong;i++){//给数组每个进行放值
        puzzleValue[i]=new PuzzleValue(scanner.nextInt(),i);
        }
    }
    public void goPuzzle(){
        invalue();
        MyStack stack=new MyStack();
        stack.push(puzzleValue[0]);
        for(int i=0;i<puzzleLong;){
            if(i+puzzleValue[i].value==(puzzleLong-1)){
                stack.push(puzzleValue[i+puzzleValue[i].value]);//入栈
                stack.show();
                break;
            }
            else if(i+puzzleValue[i].value<puzzleLong&&puzzleValue[i+puzzleValue[i].value]!=null){//如果右边可走
                if(stack.contain(stack,puzzleValue,i+puzzleValue[i].value)){//判断右边可走的值是否在栈内
                    puzzleValue[i+puzzleValue[i].value]=null;//改值为空
                }else {
                stack.push(puzzleValue[i+puzzleValue[i].value]);//入栈
                i=stack.gettop2().index;//i改为栈顶元素的下标
                }
            }else if(i-puzzleValue[i].value>0&&puzzleValue[i-puzzleValue[i].value]!=null){//左边可走
                if(stack.contain(stack,puzzleValue,i-puzzleValue[i].value)) {//判断左边可走的值是否在栈内
                    puzzleValue[i - puzzleValue[i].value] = null;//改值为空
                }else {
                    stack.push(puzzleValue[i-puzzleValue[i].value]);//入栈
                    i = stack.gettop2().index;//i改为栈顶元素的下标
                }
            }else{
                System.out.println("无路径可抵达终点");
                break;
            }
        }

    }

}

puzzlevalue类

public class PuzzleValue {

    public int value;
    public int index;
    public PuzzleValue(int value,int index){
        this.index=index;
        this.value=value;

    }

MyStake类

import java.util.Arrays;
import java.util.EmptyStackException;

public class MyStack {
    private PuzzleValue[]array2;
    private int size;
    private final int INITSIZE=10;
    public MyStack(){
                array2=new PuzzleValue[INITSIZE];

    }
    //puzzle栈
    //入栈
    public void  push(PuzzleValue puzzleValue){
        if(array.length==size){
            array2= Arrays.copyOf(array2,array2.length+(array2.length>>1));
        }else {
            array2[size]=puzzleValue;
            size++;
        }
    }

    public void pop(PuzzleValue puzzleValue){
        if(size==0){
            return;
        }else{
            array[size]=null;
            size--;
        }
    }
    //获得栈顶元素
    public PuzzleValue gettop2(){
        return array2[size-1];
    }
    //查找是否在栈内
    public  boolean contain(MyStack stack,PuzzleValue[] puzzleValue,int index){

        for(int i=0;i<size;i++){
            if(array2[i].index==index){
                return true;
            }
        }
        return false;
    }
    //打印操作
    public void show(){
        for(int i=0;i<size;i++){
            System.out.print(array2[i].value+"  ");
        }
    }
}

本文地址：https://blog.csdn.net/tdongmu/article/details/109275477