马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用---个人学习研究

gong

发布日期: 2020-08-21 10:14:20 浏览量: 99
评分:
star_border star_border star_border star_border star_border star_border star_border star_border star_border star_border
*转载请注明来自write-bug.com

创建棋盘chessBoard,是一个二维数组
将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置,每走-步,就使用step+1
遍历ArrayList中存放的所有位置,看看哪个可以走通,如果走通,就继续,走.不通,就回溯.
判断马儿是否完成了任务,使用step 和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置0 ;
注意:马儿不同的走法(策略),会得到不同的结果,效率也会有影响(优化)
*/

public class HorsechessBoard {
private static int X; // 表示列
private static int Y; // 表示行
private static boolean visited[]; // 是否被访问
private static boolean finished; // 是否全部完成

  1. // 进行行走
  2. public static void traversal(int[][] arr, int row, int col, int step) {
  3. arr[row][col] = step;
  4. visited[row * X + col] = true;// 初始位置标记为已访问
上传的附件 cloud_download HorsechessBoard.java ( 3.98kb, 0次下载 )
error_outline 下载需要2点积分
eject