frogger.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 112 行

package PKU.PRIM;
import java.util.*;
import java.math.*;

/**
 * ID:2253
 * PRIM
 * @author yhm
 * 
 */
public class Frogger {

	static int MAXNUM = Integer.MAX_VALUE;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = 1;
		while (cin.hasNext()) {
			int size = cin.nextInt();
			if (size == 0) {
				break;
			}
			int[][] xy = new int[size][2];
			for (int i = 0; i < size; i++) {
				xy[i][0] = cin.nextInt();
				xy[i][1] = cin.nextInt();
			}
			int[][] dis = new int[size][size];
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					int x = xy[i][0] - xy[j][0];
					int y = xy[i][1] - xy[j][1];
					dis[i][j] = x * x + y * y;
				}
			}

			double r = prim(dis, size);
			/*
			 * String str = r+""; String[] str1 = new String[2]; str1[0] =
			 * str.substring(0, str.indexOf('.')); str1[1] =
			 * str.substring(str.indexOf('.')+1, str.length()); int len =
			 * str1[1].length(); if(len>3){ str1[1] = str1[1].substring(0, 3); }
			 * else{ for(int k=0;k<3-len;k++){ str1[1]+="0"; } }
			 * System.out.println("Scenario #"+caseNum); System.out.print("Frog
			 * Distance = "); System.out.println(str1[0]+"."+str1[1]);
			 * System.out.println();
			 */
			BigDecimal result = new BigDecimal(r);
			r = result.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue();
			String str = r + "";
			String[] str1 = new String[2];
			str1[0] = str.substring(0, str.indexOf('.'));
			str1[1] = str.substring(str.indexOf('.') + 1, str.length());
			int len = str1[1].length();
			for (int k = 0; k < 3 - len; k++) {
				str1[1] += "0";
			}
			str = str1[0] + "." + str1[1];
			System.out.println("Scenario #" + caseNum);
			System.out.print("Frog Distance = ");
			System.out.println(str);
			System.out.println();
			caseNum++;
		}

	}

	static double prim(int[][] dis, int size) {
		int result = 0, min = MAXNUM, minIndex = 0;
		int[] low = new int[size];
		boolean[] inS = new boolean[size];
		for (int i = 0; i < size; i++) {
			low[i] = dis[0][i];
			inS[i] = false;
		}
		low[0] = 0;
		inS[0] = true;

		for (int i = 1; i < size; i++) {
			min = MAXNUM;
			for (int j = 1; j < size; j++) {
				if (!inS[j] && low[j] < min) {
					min = low[j];
					minIndex = j;
				}
			}

			result = Math.max(result, min);

			if (minIndex == 1) {
				break;
			}
			low[minIndex] = 0;
			inS[minIndex] = true;
			for (int j = 1; j < size; j++) {
				if (!inS[j] && dis[minIndex][j] < low[j]
						&& dis[minIndex][j] != MAXNUM) {
					low[j] = dis[minIndex][j];
				}
			}

		}

		return Math.sqrt(result);

	}

}