首页 > 代码库 > 算法:街区最短路径问题

算法:街区最短路径问题

package practice;import java.io.BufferedInputStream;import java.util.Arrays;import java.util.Scanner;/** * <pre> * 一个街区有很多住户,街区的街道只能为东西、南北两种方向。 *  * 住户只可以沿着街道行走。 *  * 各个街道之间的间隔相等。 *  * 用(x,y)来表示住户坐在的街区。 *  * 例如(4,20),表示用户在东西方向第4个街道,南北方向第20个街道。 *  * 现在要建一个邮局,使得各个住户到邮局的距离之和最少。 *  * 求现在这个邮局应该建在那个地方使得所有住户距离之和最小; * </pre> *  * @author caiyu * @date 2014-10-23 */public class StreetPoster {    public static void main(String[] args) {        Scanner cin = new Scanner(new BufferedInputStream(System.in));        int n = cin.nextInt();        int m;        int[][] points;        for (int i = 0; i < n; i++) {            m = cin.nextInt();            points = new int[2][m];            for (int j = 0; j < m; j++) {                points[0][j] = cin.nextInt();                points[1][j] = cin.nextInt();            }            Arrays.sort(points[0]);            Arrays.sort(points[1]);            int t = m / 2, x = points[0][t], y = points[1][t];            int sum = 0;            for (int j = 0; j < m; j++) {                sum += Math.abs(x - points[0][j]) + Math.abs(y - points[1][j]);            }            System.out.println(sum);        }    }}

 

算法:街区最短路径问题