跳马（华为od机考题）
一、题目1.原题
马是象棋(包罗中国象棋和国际象棋)中的棋子，
走法是每步直一格再斜一格，
即先横着或直着走一格，然后再斜着走一个对角线，
可进可退，可越过河界，俗称“马走‘日’字。
给顶m行n列的棋盘（网格图），
棋盘上只有有棋子象棋中的棋子“马”，
而且每个棋子有品级之分，
品级为k的马可以跳1~k步
（走的方式与象棋中“马”的规则一样，不可以超出棋盘位置），
问是否能将全部马跳到同一位置，
如果存在，输出最少需要的总步数（每匹马的步数相加），
不存在则输出-1。
注：允许不同的马在跳的过程中跳到同一位置，
坐标为(x,y)的马跳一次可以跳到到坐标为
(x+1, y+2), (x+1, y-2),
(x+2, y+1), (x+2, y-1),
(x-1, y+2), (x-1, y-2),
(x-2, y+1), (x-2, y-1),
的格点上，但是不可以超出棋盘范围。
2.题目理解
马的移动规则：先横着或直着走一格，然后再斜着走一个对角线
即每一步（x±1/2，y±2/2）
https://i-blog.csdnimg.cn/direct/f1daa2c7af144e63acf7b46727fc6c91.png
二、思路与代码过程
1.思路
每一匹马给一个board，用于记录它抵达棋盘某位置的所用步数，全部的马的board构成boards，对board进行比较即可。
2.代码过程
①main函数
public staticvoid main(String[] args) {
/*
Scanner sc = new Scanner(System.in);
System.out.println("请输入棋盘行数m：");
int m = sc.nextInt();
System.out.println("请输入棋盘列数n：");
int n = sc.nextInt();
System.out.println("请输入马在棋盘上的分布：");
int[][] horses = new int;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
horses = sc.nextInt();
}
}
sc.close();
System.out.println(Arrays.deepToString(horses));
*/
int m = 4;
int n = 4;
int[][] horse = {{1,9,9,7},{0,3,0,6},{2,0,0,2},{1,0,3,0}};
ArrayList<Horse> horses = turnToHorse(horse);
int minStep = searhEachHorse(horses,m,n);
if (minStep==-1){
System.out.println("不能将所有马跳到同一位置");
}else {
System.out.println("能将所有马跳到同一位置，且最少需要的总步数为："+minStep);
}
} ②searhEachHorse
private static int searhEachHorse(ArrayList<Horse> horses, int m, int n) {
//每一匹马的位置和步数board组成所有马的boards
ArrayList<int[][]> boards = new ArrayList<>();
for (int i = 0; i < horses.size(); i++) {//每一匹马
//先看一匹
//for (int i = 1; i < 2; i++) {
Horse horse = horses.get(i);
if (horse.k!=0){
//每一匹马都给个board,存的是每个位置所需要的步数step（step根据k算出每个位置的最小步数！）
int[][] board = new int;
int[][] boardk = new int;
int k =horse.k;//跳步级别
System.out.println("\n"+i+"---------searchEachHorse---------");
System.out.print("当前马为："+horse.toString());
int[] horseZk = horse.getPostion();
int[][] visit = new int;
int[][] visited;
Queue<int[]> q = new LinkedList<>();//要随调用传值
q.add(horseZk);
int[][] box = new int;//传值
int level = 0;
board = findPostion(horse,m,n,visit,q,box,level);//找完位置返回含有step信息的board
boardk = boardCal(board,k);
System.out.println("--===board-k===--");
for (int[] row : board) {
System.out.println(Arrays.toString(row));
}
boards.add(boardk);
System.out.println(i+"---------searchEachHorseFinished---------\n");
}
}
//获得了所有马在棋盘上的位置和步数信息
for (int[][] board : boards) {
for (int[] row : board) {
System.out.print(Arrays.toString(row)+"\n");
}
System.out.println();
}
int totalStep = CheckBoards(m,n,boards);
return totalStep;
} ③CheckBoards
private static int CheckBoards(int m,int n,ArrayList<int[][]> boards) {
System.out.println("---------checkBoard---------");
int totalSteps = 0 ;
int[][] exist = new int;
boolean allCanArr = true;
for (int i = 0; i < m; i++) {
Arrays.fill(exist, 1); // 填充每一行
}//默认都存在
int[][] AddStep = new int;
for (int i = 0; i <m; i++) {
for (int j = 0; j < n; j++) {
int addSteps = 0;
for (int k = 0; k < boards.size(); k++) {
//System.out.println(boards.get(k));
if (boards.get(k) == 0) {//检验是否存在有马到不了的位置
exist = 0;
}
addSteps += boards.get(k);
}
AddStep = addSteps;
}
}
for (int[] row : AddStep) {
for (int val : row) {
if (val == 1) {
allCanArr = false;
}
}
System.out.println(Arrays.toString(row));
}
for (int[] existBoard : exist) {
System.out.println(Arrays.toString(existBoard));
}
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j <n; j++) {
minStep = Math.min(minStep,AddStep);
}
}
totalSteps = minStep;
System.out.println(totalSteps);
if (allCanArr) {
return totalSteps;
}else{
return -1;
}
} ④boardCal
private static int[][] boardCal(int[][] board, int k) {
int[][] boardk = new int.length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
boardk = board;
if (boardk <= k&&boardk !=-1) {//=============================2
boardk= 1;
} else if (boardk > k) {
/*小于：eg：k=2，step=5=2+2+1，step=7=2+2+2+1*/
int r = board%k;
if (r==0){
boardk =board/k;
}else {
boardk = board/k+ 1;
}
}
}
}
for (int[] row : boardk) {
System.out.println(Arrays.toString(row));
}
return boardk;
}
⑤turnToHorse
private static ArrayList<Horse> turnToHorse(int[][] horse) {
ArrayList<Horse> horses = new ArrayList<>();
for (int i = 0; i < horse.length; i++) {
for (int j = 0; j < horse.length; j++) {
int[] postion =new int;
int k = 0;
postion = i;
postion = j;
k = horse;
horses.add(new Horse(postion,k,0,0));
}
}
return horses;
} ⑥方向数组
static int[][] DIRECTION={{1,2},{1,-2},
{2,1},{2,-1},
{-1,2},{-1,-2},
{-2,1},{-2,-1}}; ⑦findPosition
static ArrayList<int[]> postions = new ArrayList<>();//协助观察
private static int[][] findPostion(Horse horse,int m,int n,int[][] visit,Queue<int[]> q,int[][]box,int level ) {
//变化量:step、level注意传值
int k = horse.k;
System.out.println("k:"+k);
box]] = -1;//=============================1
while (!q.isEmpty()) {
//队列中遍历
int[] temp = q.poll();
visit]] = 1;
///*
System.out.println("到当前马"+Arrays.toString(temp)+"的访问列表：");
for (int[] row : visit) {
System.out.println(Arrays.toString(row));
}
if (Arrays.stream(visit)
.flatMapToInt(Arrays::stream) // 将二维数组扁平化为一维流
.allMatch(value -> value == 1)){
return visit;
}
// */
System.out.println("-------findPostion-------");
int size = q.size();
System.out.println("加之前q的大小："+size);
for (int[] direction : DIRECTION) {
int x = temp+ direction;
int y = temp + direction;
//System.out.println("("+x+","+y+")");
int[] Z = {x,y};
boolean contains = false;
for (int[] currentArray : q) {
if (Arrays.equals(currentArray, Z)) {
contains = true; // 找到相同的数组
}
}
if (x>=0&&x<n&&y>=0&&y<m&&visit==0&&!contains) {//只加入没去过的点
postions.add(Z);//协助观察
q.add(Z);
}
}
int size1 = q.size();
System.out.println("加之后q的大小："+size1);
System.out.println("到前马"+Arrays.toString(temp)+"时的q队列：");
int newadd = size1 - size;
System.out.println("新增了："+newadd+"个元素");
/*写到这里了，层级的自增！！！！！！！！！*/
if(newadd>0){
level++;
}
List<int[]> list = new ArrayList<>(q);
for (int i = size1-1; i >=size; i--) {
box]] = level;
}
System.out.println("===box===");
for (int[] row : box) {
System.out.println(Arrays.toString(row));
}
for (int[] element : q) {
System.out.println(Arrays.toString(element));
}
findPostion(horse,m,n,visit,q,box,level);
}
//return visit;
return box;
} ⑧Horse类（可不建）
public static class Horse{
int[] postion;
int k;
int level;
int step;
public Horse(int[] postion, int k, int level,int step) {
this.postion = postion;
this.k = k;
this.level = level;
this.step = step;
}
public String toString(){
return "坐标：["+postion+","+postion+"],等级："+k+",当前层级："+level+"当前步数："+step+"\n";
}
public int getK(){
return k;
}
public int getLevel(){
return level;
}
public int[] getPostion(){
return postion;
}
} 三、运行效果
1.运行截图
https://i-blog.csdnimg.cn/direct/c6979f945fb24ef5b6970543df4c4791.png
2.带数据分析运行效果
0---------searchEachHorse---------
当前马为：坐标：,品级：1,当前层级：0当前步数：0
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：2
到前马时的q队列：
新增了：2个元素
===box===
[-1, 0, 0, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：4
到前马时的q队列：
新增了：3个元素
===box===
[-1, 0, 0, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：5
到前马时的q队列：
新增了：2个元素
===box===
[-1, 0, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：3
到前马时的q队列：
新增了：2个元素
===box===
[-1, 4, 3, 8]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 8]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 8]
k:1
到当前马的访问列表：
[-1, 4, 3, 8]
--===board-k===--
[-1, 4, 3, 8]
0---------searchEachHorseFinished---------
1---------searchEachHorse---------
当前马为：坐标：,品级：9,当前层级：0当前步数：0
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：3
到前马时的q队列：
新增了：3个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：4
到前马时的q队列：
新增了：2个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：6
到前马时的q队列：
新增了：3个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：8
到前马时的q队列：
新增了：3个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：7
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：7
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
--===board-k===--
1---------searchEachHorseFinished---------
2---------searchEachHorse---------
当前马为：坐标：,品级：9,当前层级：0当前步数：0
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：3
到前马时的q队列：
新增了：3个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：4
到前马时的q队列：
新增了：2个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：6
到前马时的q队列：
新增了：3个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：8
到前马时的q队列：
新增了：3个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：7
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：3
到前马时的q队列：
新增了：1个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:9
到当前马的访问列表：
--===board-k===--
2---------searchEachHorseFinished---------
3---------searchEachHorse---------
当前马为：坐标：,品级：7,当前层级：0当前步数：0
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：2
到前马时的q队列：
新增了：2个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：4
到前马时的q队列：
新增了：3个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：5
到前马时的q队列：
新增了：2个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：7
到前马时的q队列：
新增了：2个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：3
到前马时的q队列：
新增了：2个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:7
到当前马的访问列表：
--===board-k===--
3---------searchEachHorseFinished---------
5---------searchEachHorse---------
当前马为：坐标：,品级：3,当前层级：0当前步数：0
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：4
到前马时的q队列：
新增了：4个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：5
到前马时的q队列：
新增了：2个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：5
到前马时的q队列：
新增了：2个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
--===board-k===--
5---------searchEachHorseFinished---------
7---------searchEachHorse---------
当前马为：坐标：,品级：6,当前层级：0当前步数：0
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：3
到前马时的q队列：
新增了：3个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：5
到前马时的q队列：
新增了：3个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：7
到前马时的q队列：
新增了：2个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：5
到前马时的q队列：
新增了：1个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:6
到当前马的访问列表：
--===board-k===--
7---------searchEachHorseFinished---------
8---------searchEachHorse---------
当前马为：坐标：,品级：2,当前层级：0当前步数：0
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：3
到前马时的q队列：
新增了：3个元素
===box===
[-1, 0, 0, 0]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：4
到前马时的q队列：
新增了：2个元素
===box===
[-1, 0, 0, 0]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：6
到前马时的q队列：
新增了：3个元素
===box===
[-1, 0, 0, 0]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
[-1, 0, 4, 0]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
[-1, 5, 4, 0]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：8
到前马时的q队列：
新增了：3个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：7
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：7
到前马时的q队列：
新增了：1个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：5
到前马时的q队列：
新增了：1个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
[-1, 5, 4, 6]
k:2
到当前马的访问列表：
[-1, 3, 2, 3]
--===board-k===--
[-1, 5, 4, 6]
8---------searchEachHorseFinished---------
11---------searchEachHorse---------
当前马为：坐标：,品级：2,当前层级：0当前步数：0
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：3
到前马时的q队列：
新增了：3个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：4
到前马时的q队列：
新增了：2个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：6
到前马时的q队列：
新增了：3个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：6
到前马时的q队列：
新增了：1个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：8
到前马时的q队列：
新增了：3个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：7
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：5
到前马时的q队列：
新增了：1个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:2
到当前马的访问列表：
--===board-k===--
11---------searchEachHorseFinished---------
12---------searchEachHorse---------
当前马为：坐标：,品级：1,当前层级：0当前步数：0
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：2
到前马时的q队列：
新增了：2个元素
===box===
[-1, 0, 0, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：4
到前马时的q队列：
新增了：3个元素
===box===
[-1, 0, 0, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：5
到前马时的q队列：
新增了：2个元素
===box===
[-1, 0, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：6
到前马时的q队列：
新增了：2个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 0]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：3
到前马时的q队列：
新增了：2个元素
===box===
[-1, 4, 3, 8]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 8]
k:1
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
[-1, 4, 3, 8]
k:1
到当前马的访问列表：
[-1, 4, 3, 8]
--===board-k===--
[-1, 4, 3, 8]
12---------searchEachHorseFinished---------
14---------searchEachHorse---------
当前马为：坐标：,品级：3,当前层级：0当前步数：0
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：0
加之后q的巨细：3
到前马时的q队列：
新增了：3个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：4
到前马时的q队列：
新增了：2个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：6
到前马时的q队列：
新增了：3个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：8
到前马时的q队列：
新增了：3个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：8
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：7
加之后q的巨细：7
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：6
加之后q的巨细：6
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：5
加之后q的巨细：5
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：4
加之后q的巨细：4
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：4
到前马时的q队列：
新增了：1个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：3
加之后q的巨细：3
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：2
加之后q的巨细：2
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
-------findPostion-------
加之前q的巨细：1
加之后q的巨细：1
到前马时的q队列：
新增了：0个元素
===box===
k:3
到当前马的访问列表：
--===board-k===--
14---------searchEachHorseFinished---------
[-1, 4, 3, 8]
[-1, 3, 2, 3]
[-1, 4, 3, 8]
---------checkBoard---------
13
能将全部马跳到同一位置，且最少需要的总步数为：13
3.带数据分析完备代码
import javax.security.auth.kerberos.KerberosCredMessage;import java.util.*;public class test34 { public staticvoid main(String[] args) {
/*
Scanner sc = new Scanner(System.in);
System.out.println("请输入棋盘行数m：");
int m = sc.nextInt();
System.out.println("请输入棋盘列数n：");
int n = sc.nextInt();
System.out.println("请输入马在棋盘上的分布：");
int[][] horses = new int;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
horses = sc.nextInt();
}
}
sc.close();
System.out.println(Arrays.deepToString(horses));
*/
int m = 4;
int n = 4;
int[][] horse = {{1,9,9,7},{0,3,0,6},{2,0,0,2},{1,0,3,0}};
ArrayList<Horse> horses = turnToHorse(horse);
int minStep = searhEachHorse(horses,m,n);
if (minStep==-1){
System.out.println("不能将所有马跳到同一位置");
}else {
System.out.println("能将所有马跳到同一位置，且最少需要的总步数为："+minStep);
}
} private static int searhEachHorse(ArrayList<Horse> horses, int m, int n) {
//每一匹马的位置和步数board组成所有马的boards
ArrayList<int[][]> boards = new ArrayList<>();
for (int i = 0; i < horses.size(); i++) {//每一匹马
//先看一匹
//for (int i = 1; i < 2; i++) {
Horse horse = horses.get(i);
if (horse.k!=0){
//每一匹马都给个board,存的是每个位置所需要的步数step（step根据k算出每个位置的最小步数！）
int[][] board = new int;
int[][] boardk = new int;
int k =horse.k;//跳步级别
System.out.println("\n"+i+"---------searchEachHorse---------");
System.out.print("当前马为："+horse.toString());
int[] horseZk = horse.getPostion();
int[][] visit = new int;
int[][] visited;
Queue<int[]> q = new LinkedList<>();//要随调用传值
q.add(horseZk);
int[][] box = new int;//传值
int level = 0;
board = findPostion(horse,m,n,visit,q,box,level);//找完位置返回含有step信息的board
boardk = boardCal(board,k);
System.out.println("--===board-k===--");
for (int[] row : board) {
System.out.println(Arrays.toString(row));
}
boards.add(boardk);
System.out.println(i+"---------searchEachHorseFinished---------\n");
}
}
//获得了所有马在棋盘上的位置和步数信息
for (int[][] board : boards) {
for (int[] row : board) {
System.out.print(Arrays.toString(row)+"\n");
}
System.out.println();
}
int totalStep = CheckBoards(m,n,boards);
return totalStep;
} private static int CheckBoards(int m,int n,ArrayList<int[][]> boards) {
System.out.println("---------checkBoard---------");
int totalSteps = 0 ;
int[][] exist = new int;
boolean allCanArr = true;
for (int i = 0; i < m; i++) {
Arrays.fill(exist, 1); // 填充每一行
}//默认都存在
int[][] AddStep = new int;
for (int i = 0; i <m; i++) {
for (int j = 0; j < n; j++) {
int addSteps = 0;
for (int k = 0; k < boards.size(); k++) {
//System.out.println(boards.get(k));
if (boards.get(k) == 0) {//检验是否存在有马到不了的位置
exist = 0;
}
addSteps += boards.get(k);
}
AddStep = addSteps;
}
}
for (int[] row : AddStep) {
for (int val : row) {
if (val == 1) {
allCanArr = false;
}
}
System.out.println(Arrays.toString(row));
}
for (int[] existBoard : exist) {
System.out.println(Arrays.toString(existBoard));
}
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j <n; j++) {
minStep = Math.min(minStep,AddStep);
}
}
totalSteps = minStep;
System.out.println(totalSteps);
if (allCanArr) {
return totalSteps;
}else{
return -1;
}
} private static int[][] boardCal(int[][] board, int k) {
int[][] boardk = new int.length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
boardk = board;
if (boardk <= k&&boardk !=-1) {//=============================2
boardk= 1;
} else if (boardk > k) {
/*小于：eg：k=2，step=5=2+2+1，step=7=2+2+2+1*/
int r = board%k;
if (r==0){
boardk =board/k;
}else {
boardk = board/k+ 1;
}
}
}
}
for (int[] row : boardk) {
System.out.println(Arrays.toString(row));
}
return boardk;
}
private static ArrayList<Horse> turnToHorse(int[][] horse) {
ArrayList<Horse> horses = new ArrayList<>();
for (int i = 0; i < horse.length; i++) {
for (int j = 0; j < horse.length; j++) {
int[] postion =new int;
int k = 0;
postion = i;
postion = j;
k = horse;
horses.add(new Horse(postion,k,0,0));
}
}
return horses;
} static int[][] DIRECTION={{1,2},{1,-2},
{2,1},{2,-1},
{-1,2},{-1,-2},
{-2,1},{-2,-1}}; static ArrayList<int[]> postions = new ArrayList<>();//协助观察
private static int[][] findPostion(Horse horse,int m,int n,int[][] visit,Queue<int[]> q,int[][]box,int level ) {
//变化量:step、level注意传值
int k = horse.k;
System.out.println("k:"+k);
box]] = -1;//=============================1
while (!q.isEmpty()) {
//队列中遍历
int[] temp = q.poll();
visit]] = 1;
///*
System.out.println("到当前马"+Arrays.toString(temp)+"的访问列表：");
for (int[] row : visit) {
System.out.println(Arrays.toString(row));
}
if (Arrays.stream(visit)
.flatMapToInt(Arrays::stream) // 将二维数组扁平化为一维流
.allMatch(value -> value == 1)){
return visit;
}
// */
System.out.println("-------findPostion-------");
int size = q.size();
System.out.println("加之前q的大小："+size);
for (int[] direction : DIRECTION) {
int x = temp+ direction;
int y = temp + direction;
//System.out.println("("+x+","+y+")");
int[] Z = {x,y};
boolean contains = false;
for (int[] currentArray : q) {
if (Arrays.equals(currentArray, Z)) {
contains = true; // 找到相同的数组
}
}
if (x>=0&&x<n&&y>=0&&y<m&&visit==0&&!contains) {//只加入没去过的点
postions.add(Z);//协助观察
q.add(Z);
}
}
int size1 = q.size();
System.out.println("加之后q的大小："+size1);
System.out.println("到前马"+Arrays.toString(temp)+"时的q队列：");
int newadd = size1 - size;
System.out.println("新增了："+newadd+"个元素");
/*写到这里了，层级的自增！！！！！！！！！*/
if(newadd>0){
level++;
}
List<int[]> list = new ArrayList<>(q);
for (int i = size1-1; i >=size; i--) {
box]] = level;
}
System.out.println("===box===");
for (int[] row : box) {
System.out.println(Arrays.toString(row));
}
for (int[] element : q) {
System.out.println(Arrays.toString(element));
}
findPostion(horse,m,n,visit,q,box,level);
}
//return visit;
return box;
} public static class Horse{
int[] postion;
int k;
int level;
int step;
public Horse(int[] postion, int k, int level,int step) {
this.postion = postion;
this.k = k;
this.level = level;
this.step = step;
}
public String toString(){
return "坐标：["+postion+","+postion+"],等级："+k+",当前层级："+level+"当前步数："+step+"\n";
}
public int getK(){
return k;
}
public int getLevel(){
return level;
}
public int[] getPostion(){
return postion;
}
}}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]