《程序员》算法擂台：骑士聚会

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

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

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<pointList.length;k++) {      
            int day = ((int[][])pointList[k])[i][j];      
            distance += day;      
            if(maxDay<day) {      
                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<points.length;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);   
                }   
            }   
        }    
    }      
}