在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士每天可以像国际象棋中的马那样移动一次，可以从中间向8个方向移动，请你计算n个骑士的最早聚会地点和要走多少天，要求尽早聚会，且n个人走的总步数最少，先到聚会地点的骑士可以不再移动等待其他的骑士。
从键盘输入n（0<n<=64），然后一次输入n个其实的初始位置xi，yi（0<=xi,y<=7）。屏幕输出以空格分割的三个数，分别为聚会的点（x，y） 以及要走的天数。
　○　○　
○　　　○
　　◎
○　　　○
　○　○　
骑士走法（中间为起始位置，空为走到位置）

我不会，做不出来。暂时没有答案。你们研究算法的做做

点集类

package convex;

import queue.Queue;

import java.util.ArrayList;
import java.util.List;

import time.MethodTimeProxy;

public class Point {

	public int x, y;

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

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

	public int distanceSq(Point p1, Point p2) {
		djkst(p1, p2);
		return shortPath[p2.x][p2.y];
	}

	//迪杰科斯特最短路径     
	private void djkst(Point p1, Point p2) {
		Queue<Point> queue = new Queue<Point>();
		flg[p1.x][p1.y] = true;
		queue.addQueue(p1);
		while (!queue.isEmpty() && !queue.front().equals(p2)) {
			Point temp = queue.front();
			queue.deleteQueue();
			List<Point> list = getList(temp);
			int i = 0;
			while (i < list.size()) {
				Point w = list.get(i);
				if (!flg[w.x][w.y]) {
					shortPath[w.x][w.y] = shortPath[temp.x][temp.y] + 1;
					queue.addQueue(w);
					flg[w.x][w.y] = true;
				}
				i++;
			}
		}
	}

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

	public Point() {
	}

	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;
	}

	public static void main(String[] args) {
		Point p1 = new Point(3, 3);
		Point p2 = new Point(0, 0);
		MethodTimeProxy proxy = new MethodTimeProxy();
		Point p = (Point) proxy.MethodTimeFactory(Point.class);
		int cc = p.distanceSq(p1, p2);
		System.out.println(cc);
	}

	public boolean equals(Point otherPoint) {
		if (otherPoint == null) {
			return false;
		} else {
			if (this.x == otherPoint.x && this.y == otherPoint.y) {
				return true;
			}
		}
		return false;
	}
}   

算法类

package convex;   
  
import convex.Point;   
  
public class Algo {   
  
    public static int[] method(Point[] points, Point[] matrix, int i) {   
        int maxDay = 0;   
        int distance = 0;
        for (int j = 0; j < points.length; j++) {   
            int day = new Point().distanceSq(points[j], matrix[i]);   
            distance += day;   
            if (day > maxDay) {   
                maxDay = day;   
            }   
        }
        return new int[]{maxDay,distance};   
    }   
  
    public static void main(String[] args) {
        Point[] matrix = new Point[64];   
        int k = 0;
        for (int i = 0; i < 8; i++) {   
            for (int j = 0; j < 8; j++) {   
                matrix[k++] = new Point(i, j);   
            }
        }   
        Point[] points = matrix; 
        int minDay = 999999999;   
        int minDistance = 999999999;
        int flg = 0;
        for (int i = 0; i < 64; i++) {
            int[] result = Algo.method(points, matrix, i);   
            if (minDay > result[0]) {
                minDay = result[0];
                minDistance = result[1];
                flg = i;
            } else if(minDay == result[0]) {
            	if(minDistance > result[1]) {
            		minDistance = result[1];
            		flg = i;
            	}
            }
        } 
        System.out.println("min x,y=" + matrix[flg]);   
        System.out.println("minDay=" + minDay); 
        System.out.println("minDistance=" + minDistance); 
    }
}

我自己写的辅助类，一个队列（写图算法时做的）

package queue;

public class Queue<E> {
	public GraphNode first;
	public GraphNode last;
	public int count;
	public void addQueue(E info) {
		GraphNode node = new GraphNode();
		node.info = info;
		if(first == null) {
			first = node;
			last = node;
		} else {
			last.link = node;
			last = last.link;
		}
		count++;
	} 
	
	public void deleteQueue() {
		if(first == null) {
			throw new RuntimeException("empty queue!");
		} else {
			first = first.link;
			count--;
		}
	}
	
	public boolean isEmpty() {
		return count == 0;
	}
	
	public E front() {
		if(first == null) {
			throw new RuntimeException("empty queue!");
		}
		return (E)first.info;
	}
	
	public E back() {
		if(last == null) {
			throw new RuntimeException("empty queue!");
		}
		return (E)last.info;
	}
}

当然还少不了一个节点

package graph;

/**
 * @author B.Chen
 *
 */
public class GraphNode {

    /**
     * 下一节点引用
     */
    public GraphNode link;

    /**
     * 值
     */
    public Object info;
}

8×8矩阵耗时8秒左右，完整算法，做了一点优化

我自己进行了一点优化，进行了一些减支之后，运行时间缩短到4秒左右time=4188ms

其中Point类里增加的main函数，大家可以来查看2点之间需要的步数，欢迎指正。期待优化

最严重的错误是 人家说的是骑士，要按照骑士的步伐来走，相差一格要走很多歩，不是距离最短就走的天数最少，他们是国际象棋的马，不是国际象棋的王。
还有就是不推荐穷举发。没有性能可言。

正确性和性能一个都不能少。

计算距离的算法应该相应的改改，然后这个穷举就差不多成立了。然后按照64个骑士测一下，看看性能。

靠 你们一天都干吗 整出个这么难的题来折磨自己 我工作几个月了 没有碰过算法

算法就是为了让自己不麻木。做对日做久了就麻木了。

同感同感