您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

马踏棋盘(图文)

第十三双眼睛2023-10-24【数据结构与算法】人已围观

简介马踏棋盘

马踏棋盘

package com.xingchen.day017;
import java.awt.*;
import java.util.ArrayList;
import java.util.List;
public class HorseChessBoard {
private static int X ;//表示棋盘的列
private static int Y ; //表示棋盘的行
// 创建一个数组来标记棋盘的各个位置是否被访问过
private static boolean[] visited;
//使用一个属性，标记棋盘的所有位置是否都被访问过
private static boolean finish;
public static void main(String[] args) {
X = 6;
Y = 6;
int row = 1;
int column = 1;
//创建棋盘
int[][] chessBoard = new int[X][Y];
visited = new boolean[X * Y];
travel(chessBoard, row - 1, column -1 ,1);
for (int[] rowss: chessBoard) {
for (int col : rowss) {
System.out.print(col+" ");
}
System.out.println("");
}
}
/**
*
* @param chessBorard 棋盘
* @param row 行
* @param column 列
* @param step 步数
*/
public static void travel(int[][] chessBorard,int row, int column, int step) {
chessBorard[row][column] = step;
visited[row * X + column] = true;
//获取可以走的下一个位置
List<Point> ps = next(new Point(column, row));
while (!ps.isEmpty()) {
Point p = ps.remove(0);
//判断该店是否已经访问过了
if (!visited[p.y * X + p.x]) {
travel(chessBorard, p.y,p.x, step + 1);
}
}
if (step < X * Y && !finish) {
chessBorard[row][column] = 0;
visited[row * X + column] = false;
} else {
finish = true;
}

}
//根据当前位置，计算还能访问哪些位置
public static List<Point> next(Point current) {
List<Point> ps = new ArrayList<>();
Point p1 = new Point();
//5
if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y - 1) >= 0) {
ps.add(new Point(p1));
}
//6
if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y - 2) >= 0) {
ps.add(new Point(p1));
}
//7
if ((p1.x = current.x + 1) < X && (p1.y = current.y - 2) >= 0) {
ps.add(new Point(p1));
}
//0
if ((p1.x = current.x + 2) < X && (p1.y = current.y - 1) >= 0) {
ps.add(new Point(p1));
}
//1
if ((p1.x = current.x + 2) < X && (p1.y = current.y + 1) < Y) {
ps.add(new Point(p1));
}
//2
if ((p1.x = current.x + 1) < X && (p1.y = current.y + 2) < Y) {
ps.add(new Point(p1));
}
//3
if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y + 2) < Y) {
ps.add(new Point(p1));
}
//4
if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y + 1) < Y) {
ps.add(new Point(p1));
}
return ps;
}
}

用贪心算法改造：

package com.xingchen.day017;
import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class HorseChessBoard {
private static int X ;//表示棋盘的列
private static int Y ; //表示棋盘的行
// 创建一个数组来标记棋盘的各个位置是否被访问过
private static boolean[] visited;
//使用一个属性，标记棋盘的所有位置是否都被访问过
private static boolean finish;
public static void main(String[] args) {
X = 8;
Y = 8;
int row = 1;
int column = 1;
//创建棋盘
int[][] chessBoard = new int[X][Y];
visited = new boolean[X * Y];
travel(chessBoard, row - 1, column -1 ,1);
for (int[] rowss: chessBoard) {
for (int col : rowss) {
System.out.print(col+" ");
}
System.out.println("");
}
}
/**
*
* @param chessBorard 棋盘
* @param row 行
* @param column 列
* @param step 步数
*/
public static void travel(int[][] chessBorard,int row, int column, int step) {
chessBorard[row][column] = step;
visited[row * X + column] = true;
//获取可以走的下一个位置
List<Point> ps = next(new Point(column, row));
//对ps进行排序
ssort(ps);
while (!ps.isEmpty()) {
Point p = ps.remove(0);
//判断该店是否已经访问过了
if (!visited[p.y * X + p.x]) {
travel(chessBorard, p.y,p.x, step + 1);
}
}
if (step < X * Y && !finish) {
chessBorard[row][column] = 0;
visited[row * X + column] = false;
} else {
finish = true;
}

}
//根据当前位置，计算还能访问哪些位置
public static List<Point> next(Point current) {
List<Point> ps = new ArrayList<>();
Point p1 = new Point();
//5
if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y - 1) >= 0) {
ps.add(new Point(p1));
}
//6
if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y - 2) >= 0) {
ps.add(new Point(p1));
}
//7
if ((p1.x = current.x + 1) < X && (p1.y = current.y - 2) >= 0) {
ps.add(new Point(p1));
}
//0
if ((p1.x = current.x + 2) < X && (p1.y = current.y - 1) >= 0) {
ps.add(new Point(p1));
}
//1
if ((p1.x = current.x + 2) < X && (p1.y = current.y + 1) < Y) {
ps.add(new Point(p1));
}
//2
if ((p1.x = current.x + 1) < X && (p1.y = current.y + 2) < Y) {
ps.add(new Point(p1));
}
//3
if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y + 2) < Y) {
ps.add(new Point(p1));
}
//4
if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y + 1) < Y) {
ps.add(new Point(p1));
}
return ps;
}
public static void ssort(List<Point> ps) {
ps.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
int c1 = next(o1).size();
int c2 = next(o2).size();
if (c1 < c2) {
return -1;
} else if (c1== c2) {
return 0;
}
return 1;
}
});
}
}

Tags：

很赞哦！ ()

上一篇：弗洛伊德算法(图文)

下一篇：两数之和