马踏棋盘算法(骑士周游问题)
关于什么是马踏棋盘,伙伴们可以自行百度,关于4399还有小游戏思路分析:package com.self.tenAlgorithm;import java.awt.*;import java.util.ArrayList;import java.util.Scanner;public class Demo7 {private static int X; // 棋盘的列数...
·
关于什么是马踏棋盘,伙伴们可以自行百度,关于4399还有小游戏
思路分析:
package com.self.tenAlgorithm;
import java.awt.*;
import java.util.ArrayList;
import java.util.Scanner;
public class Demo7 {
private static int X; // 棋盘的列数
private static int Y; // 棋盘的行数
private static boolean visited[]; // 用来标记棋盘上各个位置是否被访问过
private static boolean finished; // 用来标记是否期盼所有位置均被访问(意味着已成功)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入棋盘的行数和列数：");
do{
Y = sc.nextInt();
X = sc.nextInt();
}while(X <= 0 || Y <= 0);
System.out.print("请输入起始位置(先行数后列数)：");
int row, column;
do{
row = sc.nextInt();
column = sc.nextInt();
}while(row <= 0 || row > Y || column <= 0 || column > X);
int[][] chessBoard = new int[Y][X];
visited = new boolean[X * Y];
long start = System.currentTimeMillis();
traversalChessBoard(chessBoard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println("共耗时：" + (end - start) + "ms");
for(int[] rows : chessBoard){
for(int columns : rows){
System.out.print(columns + "\t");
}
System.out.println();
}
sc.close();
}
public static void traversalChessBoard(int[][] chessBoard, int row, int column, int step) {
chessBoard[row][column] = step;
visited[row * X + column] = true; // 此位置已访问
ArrayList<Point> ps = next(new Point(column, row)); // 由当前位置得到下一次所有位置的集合
while (!ps.isEmpty()) {
Point p = ps.remove(0);
if (!visited[p.y * X + p.x]) { // 这个位置没有访问，那么就从这个位置开始进行下一次访问
traversalChessBoard(chessBoard, p.y, p.x, step + 1);
}
}
if(step < X * Y && !finished){ // (step < X * Y)这个条件成立，有两种情况：第一种，棋盘到目前为止仍没有走完;第二种，棋盘已经走完过，此时在回溯的过程中
chessBoard[row][column] = 0; // 如果整个棋盘最终全部为零，则表示无解
visited[row * X + column] = false;
}else{
finished = true;
}
}
// 在当前位置p处，下一次的位置(最多有8个位置)
public static ArrayList<Point> next(Point p) {
ArrayList<Point> ps = new ArrayList<Point>();
Point p1 = new Point(p);
if ((p1.x = p.x - 2) >= 0 && (p1.y = p.y - 1) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x - 1) >= 0 && (p1.y = p.y - 2) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 1) < X && (p1.y = p.y - 2) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 2) < X && (p1.y = p.y - 1) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 2) < X && (p1.y = p.y + 1) < Y) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 1) < X && (p1.y = p.y + 2) < Y) {
ps.add(new Point(p1));
}
if ((p1.x = p.x - 1) >= 0 && (p1.y = p.y + 2) < Y) {
ps.add(new Point(p1));
}
if ((p1.x = p.x - 2) >= 0 && (p1.y = p.y + 1) < Y) {
ps.add(new Point(p1));
}
return ps;
}
}
可能是我的电脑性能不是很好,耗时比较长
请输入棋盘的行数和列数：8 8
请输入起始位置(先行数后列数)：3 1
共耗时：248758ms
9 2 11 16 25 4 13 64
18 21 8 3 12 15 26 5
1 10 17 20 7 24 63 14
54 19 22 33 62 45 6 27
41 32 55 50 23 34 61 46
56 53 40 31 44 49 28 35
39 42 51 58 37 30 47 60
52 57 38 43 48 59 36 29
贪心算法优化处理
private static int X; // 棋盘的列数
private static int Y; // 棋盘的行数
private static boolean visited[]; // 用来标记棋盘上各个位置是否被访问过
private static boolean finished; // 用来标记是否期盼所有位置均被访问(意味着已成功)
private static int count = 1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
do{
System.out.print("请输入棋盘的行数和列数：");
Y = sc.nextInt();
X = sc.nextInt();
}while(X <= 0 || Y <= 0);
int row, column;
do{
System.out.print("请输入起始位置(先行数后列数)：");
row = sc.nextInt();
column = sc.nextInt();
}while(row <= 0 || row > Y || column <= 0 || column > X);
int[][] chessBoard = new int[Y][X];
visited = new boolean[X * Y];
long start = System.currentTimeMillis();
traversalChessBoard(chessBoard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println("共耗时：" + (end - start) + "ms");
for(int[] rows : chessBoard){
for(int columns : rows){
System.out.print(columns + "\t");
}
System.out.println();
}
sc.close();
}
public static void traversalChessBoard(int[][] chessBoard, int row, int column, int step) {
chessBoard[row][column] = step;
visited[row * X + column] = true; // 此位置已访问
ArrayList<Point> ps = next(new Point(column, row)); // 由当前位置得到下一次所有位置的集合
sort(ps); // 按照当前(new Point(column, row))这步的下一步的下一步选择数目进行非递减排序
while (!ps.isEmpty()) {
Point p = ps.remove(0); // 每次选择仍然未选中的下一步的下一步选择数目最少的下一步作为当前这步的下一步
if (!visited[p.y * X + p.x]) { // 这个位置没有访问，那么就从这个位置开始进行下一次访问
traversalChessBoard(chessBoard, p.y, p.x, step + 1);
}
}
if(step < X * Y && !finished){ // (step < X * Y)这个条件成立，有两种情况：第一种，棋盘到目前为止仍没有走完;第二种，棋盘已经走完过，此时在回溯的过程中
chessBoard[row][column] = 0; // 如果整个棋盘最终全部为零，则表示无解
visited[row * X + column] = false;
}else{ // 此处代表已成功走出覆盖棋盘的完整路径，如果此时将结果输出(去掉finished变量)，以便回溯可以得到所有的结果
finished = true;
}
}
// 在当前位置p处，下一次的位置(最多有8个位置)
public static ArrayList<Point> next(Point p) {
ArrayList<Point> ps = new ArrayList<Point>();
Point p1 = new Point(p);
if ((p1.x = p.x - 2) >= 0 && (p1.y = p.y - 1) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x - 1) >= 0 && (p1.y = p.y - 2) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 1) < X && (p1.y = p.y - 2) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 2) < X && (p1.y = p.y - 1) >= 0) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 2) < X && (p1.y = p.y + 1) < Y) {
ps.add(new Point(p1));
}
if ((p1.x = p.x + 1) < X && (p1.y = p.y + 2) < Y) {
ps.add(new Point(p1));
}
if ((p1.x = p.x - 1) >= 0 && (p1.y = p.y + 2) < Y) {
ps.add(new Point(p1));
}
if ((p1.x = p.x - 2) >= 0 && (p1.y = p.y + 1) < Y) {
ps.add(new Point(p1));
}
return ps;
}
// 根据当前的这一步的所有下一步的选择数目进行非递减排序
public static void sort(ArrayList<Point> ps){
ps.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
int count1 = next(o1).size(); // 当前这一步o1的下一步的选择数目
int count2 = next(o2).size();
if (count1 < count2) {
return -1;
} else if (count1 == count2) {
return 0;
} else {
return 1;
}
}
});
}
结果展示
请输入棋盘的行数和列数：8 8
请输入起始位置(先行数后列数)：3 1
共耗时：13ms
29 2 43 18 31 4 45 20
42 17 30 3 44 19 32 5
1 28 53 56 63 60 21 46
16 41 62 59 54 57 6 33
27 12 55 52 61 64 47 22
40 15 38 25 58 51 34 7
11 26 13 50 9 36 23 48
14 39 10 37 24 49 8 35
昇腾计算产业是基于昇腾系列（HUAWEI Ascend）处理器和基础软件构建的全栈 AI计算基础设施、行业应用及服务，https://devpress.csdn.net/organization/setting/general/146749包括昇腾系列处理器、系列硬件、CANN、AI计算框架、应用使能、开发工具链、管理运维工具、行业应用及服务等全产业链
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)