当前位置： 首页 > article >正文

Java语言程序设计基础篇_编程练习题***18.32 (游戏:骑士的旅途)

article 2024/11/13 9:17:51

目录

题目：***18.32 (游戏:骑士的旅途)

习题思路

代码示例

 输出结果

题目：***18.32 (游戏:骑士的旅途)

骑士的旅途是一个古老的谜题，它的目的是使骑从棋盘上的任意一个正方 形开始移动，经过其他的每个正方形一次，如图18-15a 所示。注意，骑士只能做L形的移动(两个空格在一个方向上而一个空格在垂直的方向上)。如图18-15b 所示，骑士可以移动到八个正方形的位置。编写一个程序，显示骑士的移动，如图 18-15C 所示。当单击一个单元格的时候，骑士被放置在该单元格中。该单元格作为骑士的起始点。单击Solve按钮显示作为解答的路径。

  • 习题思路
  1. 界面设置：
    • 使用BorderPane作为主布局，中心放置一个Board（自定义的Pane），用于绘制棋盘和骑士的移动路径。
    • 在底部添加一个按钮btSolve，用于触发求解过程。
    • 舞台（Stage）和场景（Scene）的设置，包括尺寸和标题。
  2. 棋盘和骑士的初始化：
    • 在Board类中，通过draw方法绘制棋盘（网格线）和初始位置的骑士（红色圆圈）。
    • 骑士的初始位置（startX和startY）默认为(0, 0)，但可通过鼠标点击棋盘上的任意格子来设置新的起始位置。
  3. 求解逻辑：
    • 使用一个二维布尔数组moves来记录棋盘上的格子是否已被访问过。
    • solvePuzzle方法是一个递归函数，用于尝试不同的移动路径，直到找到一种能够遍历所有格子并返回起点的解决方案。
    • 在每一步尝试中，通过lookAheadCount方法评估每个可能的下一步移动，并选择看起来最有前景的（即下一步后能够访问最多新格子的）移动。
    • 使用回溯法，如果当前路径无法找到解决方案，则撤销上一步的选择，尝试其他可能的移动。
  4. 用户交互：
    • 点击棋盘上的格子设置新的起始位置，并清空之前的移动历史。
    • 点击“Solve”按钮触发求解过程，并在找到解决方案后重新绘制棋盘，显示骑士的移动路径。
  5. 移动历史记录：
    • 使用ArrayList<Point2D>来记录骑士的移动历史，以便在求解过程中回溯和重新绘制路径。
    • 提供resetMoves、addMove和removeLastMoveHistory方法来管理移动历史记录。
  6. 棋盘绘制：
    • 在Board类的draw方法中，除了绘制棋盘网格和骑士外，还根据移动历史记录绘制骑士的移动路径。
  • 代码示例

编程练习题18_32TheKnightJourney.java

package chapter_18;  
  
import java.util.ArrayList;
import java.util.List;
import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.geometry.Pos;  
import javafx.scene.Scene;  
import javafx.scene.control.Button;  
import javafx.scene.layout.BorderPane;  
import javafx.scene.layout.HBox;  
import javafx.scene.layout.Pane;  
import javafx.scene.paint.Color;  
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.stage.Stage;  
  
public class 编程练习题18_32TheKnightJourney extends Application {  
	private static final int SIZE = 8;
	private int startX = 0;
	private int startY = 0;
	private ArrayList<Point2D> moves = null;
	public static void main(String[] args) {  
		Application.launch(args);  
	}  
    @Override  
    public void start(Stage primaryStage) throws Exception {
    	BorderPane pane = new BorderPane();
    	Board board = new Board();
    	pane.setCenter(board);
    	Button btSolve = new Button("Solve");
    	pane.setBottom(btSolve);
    	BorderPane.setAlignment(btSolve, Pos.CENTER);
    	
    	Scene scene = new Scene(pane,400,400);
    	primaryStage.setTitle("");
    	primaryStage.setScene(scene);
    	primaryStage.show();
    	
    	board.draw();
    	
    	btSolve.setOnAction(e -> {
    		boolean[][] moves = new boolean[SIZE][SIZE];
    		moves[startX][startY] = true;
    		resetMoves();
    		addMove(startX,startY);
    		solvePuzzle(moves,1,startX,startY);
    		board.draw();
    	});
    }
    
    private boolean solvePuzzle(boolean[][] moves,int numberMoves,int x,int y) {
    	int nextX = 0;
    	int nextY = 0;
    	int bestMoveX = 0;
    	int bestMoveY = 0;
    	int bestMoveX2 = 0;
    	int bestMoveY2 = 0;
    	int minMoveCount = SIZE;
    	int moveCount = 0;
    	
    	for(int i = 2;i >= -2;i += -4) {
    		for(int j = 1;j >= -1;j += -2) {
    			nextX = x + i;
    			nextY = y + j;
    			if(nextX >= 0&&nextX <= SIZE-1&&nextY >= 0&&nextY <= SIZE-1
    					&&!moves[nextX][nextY]) {
    				moveCount = lookAheadCount(moves,nextX,nextY);
    				if(moveCount <= minMoveCount) {
    					minMoveCount = moveCount;
    					bestMoveX2 = bestMoveX;
    					bestMoveY2 = bestMoveY;
    					bestMoveX = nextX;
    					bestMoveY = nextY;
    				}
    			}
    			nextX = x + j;
    			nextY = y + i;
    			if(nextX >= 0&&nextX <= SIZE-1&&nextY >= 0&&nextY <= SIZE-1
    					&&!moves[nextX][nextY]) {
    				moveCount = lookAheadCount(moves,nextX,nextY);
    				if(moveCount <= minMoveCount) {
    					minMoveCount = moveCount;
    					bestMoveX2 = bestMoveX;
    					bestMoveY2 = bestMoveY;
    					bestMoveX = nextX;
    					bestMoveY = nextY;
    				}
    			}
    		}
    	}
    	moves[bestMoveX][bestMoveY] = true;
    	addMove(bestMoveX,bestMoveY);
    	numberMoves++;
    	if(numberMoves == (SIZE * SIZE))
    		return true;
    	if(moveCount > 0&&solvePuzzle(moves, numberMoves, bestMoveX, bestMoveY))
    		return true;
    	moves[bestMoveX][bestMoveY] = false;
    	moves[bestMoveX2][bestMoveY2] = true;
    	removeLastMoveHistory();
    	addMove(bestMoveX2,bestMoveY2);
    	if(moveCount > 1&&solvePuzzle(moves, numberMoves, bestMoveX2, bestMoveY2)) {
    		return true;
    	}
    	moves[bestMoveX2][bestMoveY2] = false;
    	removeLastMoveHistory();
    	numberMoves--;
    	return false;
    }
    private int lookAheadCount(boolean[][] moves,int x,int y) {
    	int maxCount = 0;
    	for(int i = -2;i<=2;i+=4) {
    		for(int j = -1;j <= 1;j += 2) {
    			int nextX = x + i;
    			int nextY = y + j;
    			if(nextX >= 0&&nextX <= SIZE-1&&nextY >=0 && nextY <= SIZE-1
    					&&!moves[nextX][nextY]) {
    				maxCount++;
    			}
    			nextX = x + j;
    			nextY = y + i;
    			if(nextX >= 0&&nextX <= SIZE-1&&nextY >= 0&&nextY <= SIZE-1&&
    					!moves[nextX][nextY])
    				maxCount++;
    		}
    	}
    	return maxCount;
    }
    public void resetMoves() {
    	moves = new ArrayList(63);
    }
    public void addMove(int x,int y) {
    	moves.add(new Point2D(x, y));
    }
    public void removeLastMoveHistory() {
    	moves.remove(moves.size()-1);
    }
    private class Board extends Pane{
    	Circle theKnight = new Circle();
    	Board(){
    		this.setOnMouseClicked(e ->{
    			startX = (int)(e.getX()/(getWidth()/SIZE));
    			startY = (int)(e.getY()/(getHeight()/SIZE));
    			resetMoves();
    			draw();
    		});
    	}
    	protected void draw() {
    		this.getChildren().clear();
    		this.getChildren().add(theKnight);
    		theKnight.setCenterX(startX * getWidth()/SIZE +15);
    		theKnight.setCenterY(startY * getHeight()/SIZE + 15);
    		theKnight.setRadius(5);
    		theKnight.setFill(Color.RED);
    		
    		for(int i = 1;i <= SIZE;i++) {
    			this.getChildren().add(
    					new Line(0,i*getHeight()/SIZE,getWidth(),
    							i*getHeight()/SIZE));			                     
    			this.getChildren().add(
    					new Line(i*getWidth()/SIZE,0,i*getWidth()/SIZE,
    							getHeight()));
    		}
    		if(moves != null) {
    			for(int i = 1;i < moves.size();i++) {
    				Point2D p1 = moves.get(i - 1);
    				Point2D p2 = moves.get(i);
    				this.getChildren().add(
    						new Line(p1.getX()*(getWidth()/SIZE)+(getWidth()/SIZE/2),
    								p1.getY()*(getHeight()/SIZE)+(getHeight()/SIZE/2),
    								p2.getX()*(getWidth()/SIZE)+(getWidth()/SIZE/2),
    								p2.getY()*(getHeight()/SIZE)+(getHeight()/SIZE/2)
    				));
    			}
    		}
    	}
    }
}
  •  输出结果

 


http://www.kler.cn/a/312858.html

相关文章：

  • ESLint 使用教程（七）：ESLint还能校验JSON文件内容？
  • 【C++】详解RAII思想与智能指针
  • 从0开始学docker （每日更新 24-11-7）
  • Matlab实现鹈鹕优化算法（POA）求解路径规划问题
  • Ubuntu 的 ROS 操作系统turtlebot3环境搭建
  • AI 大模型如何赋能电商行业，引领变革
  • 排序---冒泡排序、堆排序
  • etcd三节点，其中一个坏掉了的恢复办法
  • Codeforces Round 973 (Div. 2) F1. Game in Tree (Easy Version)（思维题 博弈）
  • 以更高分辨率和体内方式了解 lncRNA 的生物发生和功能
  • neo4j(spring) 使用示例
  • spark-scala使用与安装（一）
  • Ubuntu 与Uboot网络共享资源
  • Lua编程语言简介与应用
  • 【python设计模式4】结构型模式1
  • 专利管理系统如何确保专利资产持续有效？
  • （蓝桥杯）STM32G431RBT6（TIM4-PWM）
  • 【结构型】树形结构的应用王者，组合模式
  • setImmediate() vs setTimeout() 在 JavaScript 中的区别
  • 全志A133 android10 适配EC20 4G模块
  • 开源模型应用落地-qwen模型小试-Qwen2.5-7B-Instruct-Gradio快速体验（十四）
  • 音频评价指标
  • MATLAB系列04：循环结构
  • 海外云市场分析
  • Linux编程：解析EAGAIN错误 Resource temporarily unavailable
  • neo4j节点关联路径的表示、节点的增删改查