街區最短路徑問題

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：4

描述

一個街區有很多住戶，街區的街道只能為東西、南北兩種方向。
住戶只可以沿著街道行走。
各個街道之間的間隔相等。
用(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

最佳代碼

 
#include<iostream>
#include<algorithm>
using namespace std;
int x[30],y[30],n,m,i;;
int main()
{cin>>n;while(n--){cin>>m;for(i=0;i<m;i++)cin>>x[i]>>y[i];sort(x,x+m);sort(y,y+m);int sum=0;for(i=0;i<m/2;i++)sum+=x[m-1-i]-x[i]+y[m-1-i]-y[i];cout<<sum<<endl;}return 0;
}        

sort是c++的排序函數，默認是升序。感覺比qsort容易記住。
這個想法非常好，兩點橫坐標距離差就是要走到報刊亭的橫向距離，縱向也一樣。我寫的是用窮舉法，枚舉每個位置，這種方法比較容易想，但很慢，還因為一個小錯誤提交了十幾遍....細節是最重要的呀。

#include<stdio.h>
#define MAXN 1000000int abs(int a)
{return a>0? a:(-a); 
}
int main()
{int n;scanf("%d",&n);while(n--){int m,i=0;scanf("%d",&m);int x[20],y[20];for(i=0;i<m;i++){scanf("%d%d",&x[i],&y[i]);}int j,maxx=x[0],maxy=y[0],minx=x[0],miny=y[0];for(j=0;j<m;j++){if(x[j]>maxx)maxx=x[j];if(y[j]>maxy)maxy=y[j];  if(x[j]<minx)minx=x[j];if(y[j]<miny)miny=y[j];  }int mdis=MAXN,k;for(i=minx;i<=maxx;i++){for(j=miny;j<=maxy;j++){int sum=0;for(k=0;k<m;k++){sum+=abs(x[k]-i)+abs(y[k]-j);}if(sum<mdis)mdis=sum;}}printf("%d\n",mdis);}
}

轉載于:https://www.cnblogs.com/xurenwen/p/3855483.html

總結

以上是生活随笔為你收集整理的NYOJ——街区最短路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。