骑士聚会（《程序员》的算法擂台）
 |
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
都是咱们大学学的数据结构，还有大四老师给讲的算法里的
|
