骑士聚会（《程序员》的算法擂台）讨论第2页: - Vicious--算法 - Pipboy

群组首页 → 编程语言 → Pipboy → 论坛

发表回复

[Vicious--算法] 骑士聚会（《程序员》的算法擂台）

leon_a 2007-09-06

64的性能也不会差，这个算法的复杂度本身就不高，呵呵，他们给的数据规模较小，所以暴力法也算一个选择，期待更优算法，我计算几何比较差劲，搞不了深入的数学问题

xufei0110 2007-09-06

中午想了一下，没时间写程序（这个破公司就跟监狱似的什么也不让干）
1, 求出每个骑士能走到的点的坐标集 P[n][x][y]=[];
2, 求出这些坐标集的交集，就是这些骑士可能聚会的地点坐标集
3, 求出这个聚会点坐标集里的每个点所有骑士用的时间总和集
4, 找出这个时间集里的最小值

leon_a 2007-09-06

snowind9 写道

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

嗯，做些copy的活无聊，就用恶心的算法折磨自己

leon_a 2007-09-08

进行了优化，牺牲空间来优化时间 64个骑士的运行时间在125ms

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

	//仿迪杰科斯特最短路径     
	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;
        int x = 0;
        int y = 0;
        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];
                    x = i;
                    y = j;
                } else if(minDay == result[0]) {
                	if(minDistance > result[1]) {
                		minDistance = result[1];
                        x = i;
                        y = j;
                	}
                }
        	}
        }
        //数据输出x,y点坐标，最小天数
        System.out.println("" + x+" "+y+" "+minDay);   
    }
}

leon_a 2007-09-10

仔细想了一下，这个输出应该不只有一个点所以程序修改如下

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;   
    }   
  
    //仿迪杰科斯特最短路径        
    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);
                }
            }
        } 
    }   
}

renshengjihe 2007-09-10

我怎么感觉我离计算机越来越远了啊．

leon_a 2007-09-20

都是咱们大学学的数据结构，还有大四老师给讲的算法里的

发表回复

>>返回群组首页

[Vicious--算法] 骑士聚会（《程序员》的算法擂台）

相关讨论

相关资源推荐