数据结构与算法|《程序员》算法擂台（骑士聚会） J#|算法

在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士每天可以像国际象棋中的马那样移动一次，可以从中间向8个方向移动，请你计算n个骑士的最早聚会地点和要走多少天，要求尽早聚会，且n个人走的总步数最少，先到聚会地点的骑士可以不再移动等待其他的骑士。
从键盘输入n（0　○　○
○○
◎
○○
　○　○
骑士走法（中间为起始位置，空为走到位置）
[code]
package convex;

public class Point {

public int x, y;

public Point(int x, int y) {
if (x > 7 || y > 7) {
throw new RuntimeException("out of matrix");
}
this.x = x;
this.y = y;
}

public String toString() {
return "x=" + x + ",y=" + y;
}

}
[/code]
[code]
package convex;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import convex.Point;

public class Algo {

private boolean[][] flg = new boolean[8][8];

private int[][] shortPath = new int[8][8];

//最短距离矩阵
public int[][] distanceSq(Point p1) {
djkst(p1);
return shortPath;
}

//BFS
private void djkst(Point p1) {
Point[] queue = new Point[64];
flg[p1.x][p1.y] = true;
queue[0] = p1;
int j=0;
int queueSize = 1;
while (j < queue.length) {
Point temp = queue[j];
Point[] list = getList(temp);
for(int i=0; i < list.length; i++) {
if(list[i] != null) {
Point w = list[i];
if (!flg[w.x][w.y]) {
shortPath[w.x][w.y] = shortPath[temp.x][temp.y] + 1;
queue[queueSize++] = w;
flg[w.x][w.y] = true;
}
}
}
j++;
}
}

//可行步数集
private static Point[] getList(Point point) {
Point[] list = new Point[8];
int length = 0;
if (point.x + 2 <= 7 && point.y + 1 <= 7) {
list[length++] = new Point(point.x + 2, point.y + 1);
}
if (point.x - 2 >= 0 && point.y - 1 >= 0) {
list[length++] = new Point(point.x - 2, point.y - 1);
}
if (point.x + 1 <= 7 && point.y + 2 <= 7) {
list[length++] = new Point(point.x + 1, point.y + 2);
}
if (point.x - 1 >= 0 && point.y - 2 >= 0) {
list[length++] = new Point(point.x - 1, point.y - 2);
}
if (point.x + 2 <= 7 && point.y - 1 >= 0) {
list[length++] = new Point(point.x + 2, point.y - 1);
}
if (point.x - 2 >= 0 && point.y + 1 <= 7) {
list[length++] = new Point(point.x - 2, point.y + 1);
}
if (point.x + 1 <= 7 && point.y - 2 >= 0) {
list[length++] = new Point(point.x + 1, point.y - 2);
}
if (point.x - 1 >= 0 && point.y + 2 <= 7) {
list[length++] = new Point(point.x - 1, point.y + 2);
}
return list;
}

public static int[] method(Point[] points, int i,int j,Object[] pointList) {
int maxDay = 0;
int distance = 0;
for(int k=0; k【数据结构与算法|《程序员》算法擂台（骑士聚会）】 int day = ((int[][])pointList[k])[i][j];
distance += day;
if(maxDay maxDay = day;
}
}
return new int[]{maxDay,distance};
}

public static void main(String[] args) throws IOException {
//数据输入
//数据输入格式：第一个数字是骑士n，第2，3个数字是第一个骑士的坐标，依次类推。
//每个数字之间以空格区分
BufferedReader stdin =
new BufferedReader(
new InputStreamReader(System.in));

String line = stdin.readLine();
StringTokenizer st = new StringTokenizer(line);
int pointLength = Integer.parseInt(st.nextToken());
Point[] points = new Point[pointLength];
for(int i=0; i int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points[i] = new Point(x,y);
}
Object[] pointList = new Object[points.length];
for (int j = 0; j < points.length; j++) {
pointList[j] = new Algo().distanceSq(points[j]);
}
int minDay = 999999999;
int minDistance = 999999999;
for(int i=0; i<7; i++) {
for(int j=0; j<7; j++) {
int[] result = Algo.method(points, i,j,pointList);
//找最短天数，最短天数相同，找最短距离
if (minDay > result[0]) {
minDay = result[0];
minDistance = result[1];
} else if(minDay == result[0]) {
if(minDistance > result[1]) {
minDistance = result[1];
}
}
}
}
for(int i=0; i<7; i++) {
for(int j=0; j<7; j++) {
int[] result = Algo.method(points, i,j,pointList);
if(minDay == result[0] && minDistance == result[1]) {
System.out.println(i+" " + j +" "+ minDay);
}
}
}
}
}
[/code]

数据结构与算法|《程序员》算法擂台（骑士聚会）

推荐阅读

兰瑟睫毛膏双头防水吗

睡前喝一瓶啤酒好吗

python获取linux系统信息的三种方法

放心

分析理解区别,回归和相关分析的区别

进藏日记（15）（鲁朗林海·田园风光）

国税怎么申报

冬天尿量少是什么原因为什么尿量少

人工智能|套裁问题之踩坑记

养鱼苗喂什么

两个函数调用Python 如何调用两个函数

女人一生能产生多少卵子？

苏州和南京,你觉得定居哪个城市更好？为什么？

进货

树形计数背包-HDU|树形计数背包-HDU 6540 Neko and tree

数据结构和算法|[字符串]重复的子字符串

周公解梦梦见烧纸钱是什么意思周公解梦梦见烧纸钱的含义

2021妇女节微信祝福语

冬季敷面膜敷多久冬季敷面膜敷的时间

庆东锅炉e4故障代码是什么故障,原因通常是这样的