描述
一个街区有很多住户,街区的街道只能为东西、南北两种方向。
住户只可以沿着街道行走。
各个街道之间的间隔相等。
用(x,y)来表示住户坐在的街区。
例如(4,20),表示用户在东西方向第4个街道,南北方向第20个街道。
现在要建一个邮局,使得各个住户到邮局的距离之和最少。
求现在这个邮局应该建在那个地方使得所有住户距离之和最小;
输入
第一行一个整数n<20,表示有n组测试数据,下面是n组数据;
每组第一行一个整数m<20,表示本组有m个住户,下面的m行每行有两个整数0<x,y<100,表示某个用户所在街区的坐标。
m行后是新一组的数据;
输出
每组数据输出到邮局最小的距离和,回车结束;
样例输入
2
3
1 1
2 1
1 2
5
2 9
5 20
11 9
1 1
1 20
样例输出
2
44
算法分析:
本题算法较简单,遍历所有居民长方形居住区域的每一个点,计算改点和每个居民的和,然后比较每个点到用户的长度和大小,对于多组用户则放入一个三维数组中~
代码如下:
import java.util.*;
//import java.io.*;
public class Main
{
public static void main(String[] args) throws Exception
{
Scanner input = new Scanner(System.in);
//System.out.println("请输入有几组人家");
int row = input.nextInt();
int[][][] house = new int[row][][];
for(int index = 0; index < row ; index++)
{
// System.out.println("请输入有几户人家第" + (index+1) + "组");
int num = input.nextInt();
house[index] = new int[num][2];
for(int i = 0; i < num; i++)
{
// System.out.println("请输入第" + index + "组第" + (i+1) + "户人家坐标");
house[index][i][0] = input.nextInt();
house[index][i][1] = input.nextInt();
}
}
cal(house);
}
public static void cal(int a[][][])
{
int aa = a.length;
int max = 0;
int ret = 0;
for(int i = 0; i < aa; i++)
{
int maxx = a[i][0][0];
int maxy = a[i][0][1];
int distance = 0;
int mindistance = 0;
for(int i1 = 0; i1 < a[i].length; i1++)
{
if(a[i][i1][0] > maxx)
{
maxx = a[i][i1][0];
}
}
for(int i1 = 0; i1 < a[i].length; i1++)
{
if(a[i][i1][1] > maxy)
{
maxy = a[i][i1][1];
}
}
for(int x = 0; x < maxx+1; x++)
{
for(int y = 0; y < maxy+1; y++)
{
distance = 0;
for(int i1 = 0; i1 < a[i].length; i1++)
{
distance = distance + Math.abs(x-a[i][i1][0])+Math.abs(y-a[i][i1][1]);
if((x == 0) && (y == 0))
{
mindistance = distance;
}
}
if(distance < mindistance)
mindistance = distance;
}
}
System.out.println(mindistance);
}
}
}
分享到:
相关推荐
首先提出最短路径距离在宗地地价点状因素评价中的应用模式,然后设计节点-连线-街区网络数据模型和与之相应的网络外抽象节点接入网络的规则,构造基于最短路径查询的动态网络,最后采用改进型Dijkstra算法计算出宗地...
用字符文件提供数据建立带权网络存储结构。...提示:用迪杰特斯拉算法或弗洛依德算法求出所有结点自已到自己的最短路径,选出其中的最小值即为该图的最短回路。 实验目的:掌握图的存储结构;掌握图的最短路径算法。
在Network Analyst中,缺省使用线的长度来计算两地的最短路径。 从Working Unit下拉列表中选择工作单位,工作单位确定了该路线的总的费用,例如:在该路线上行驶所需的时间或距离。如果用作为费用字段,该视图的距离...
问题描述:在一个按照东西和南北方向划分成规整街区的城市里,n个居民点散乱地分布在不同的街区中。用x坐标表示东西向,用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。要求:为建邮局选址,使得n个居民点...
武汉中山大道街区复兴规划设计方案
A-Star (A*) 最短路径寻找算法。 Bredth First Search 算法 (BFS) 深度优先搜索算法 (DFS) 您有试图从 AB 点获得的演员(人)。 他们需要一条路径(一个点队列)来遍历。 有静态方法: Model.getDeterminedPath...
街三举措实现街区“变形记”
长春市繁华街区环境问题调查报告.doc
内容简介:浙江毗邻住宅区新中式商业街区建筑方案-2021年(PDF+78页)。图纸包含:城市研究、地块研究、本案定位、案例分析、设计策略、方案展示、住宅设计、总图规划、办公地块设计、住宅地块设计、规划推导、区位...
智慧街区综合解决方案.pdf
应用地理信息系统(GIS)技术,收集历史街区的建筑、土 地利用、道路街巷、管网管线、绿化、人口信息、社会经济等资料, 建立一种基于GIS技术的历史街区现状调查、保护规划编制、日常 保护和管理控制的方法,提高...
邮局选址问题源程序 环境c++6.0 可以运行
我国历史街区保护更新规划研究与展望,石亚灵,黄勇,为保护我国历史街区,明确历史街区概念,加强历史街区保护更新理论的针对性,强化历史街区实践的特色性,通过回顾历史街区及其保
智慧街区物联网.pdf
“智慧街区”项目建设方案
智慧街区NB-IoT物联网方案
购物街区音乐跨年嘉年华活动策划案.pptx
上坤·上街商业街区包装方案.pdf
商业街区游戏嘉年华活动方案.pptx
2020城市更新白皮书系列:历史文化街区的活化迭代-202011精品报告2020.pdf