时间戳

首页 > 技术文章 > 物流中转站

物流中转站

cstdio1 2019-07-20 13:38 原文

题目描述

Shopee物流会有很多个中转站。在选址的过程中，会选择离用户最近的地方建一个物流中转站。

假设给你一个二维平面网格，每个格子是房子则为1，或者是空地则为0。找到一个空地修建一个物流中转站，使得这个物流中转站到所有的房子的距离之和最小。 能修建，则返回最小的距离和。如果无法修建，则返回 -1。

 

若范围限制在100*100以内的网格，如何计算出最小的距离和？

当平面网格非常大的情况下，如何避免不必要的计算？

 

输入描述:

4
0 1 1 0
1 1 0 1
0 0 1 0
0 0 0 0

先输入方阵阶数，然后逐行输入房子和空地的数据，以空格分隔。

输出描述:

8

能修建，则返回最小的距离和。如果无法修建，则返回 -1。
示例1

输入

复制 
4
0 1 1 0
1 1 0 1
0 0 1 0
0 0 0 0

输出

复制 
8

说明

 
示例2

输入

复制 
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出

复制 
-1
解题思路：直接遍历即可

#include "iostream"
#include "cstring"
#include "algorithm"
#include "cmath"
#include "set" 
using namespace std;

const int maxn=200; 
int path[maxn][maxn];
bool judge(int size)//判断是否可以建中转站 
{
    for(int i=0;i<size;i++){
    for(int j=0;j<size;j++){
        if(path[i][j]==0) return true;
    }
    }return false;
}
int main()
{
int size;
while(cin>>size)
{    
memset(path,1,sizeof(path));    
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
cin>>path[i][j];
if(judge(size)==0) cout<<-1<<endl;
else{int best_value=999999;//假设最好的路长度是999999 
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){    
    if(path[i][j]==0){ int s=0;//path[i][j]==0可以作为中转站，进行判断 
        for(int ii=0;ii<size;ii++){
            for(int jj=0;jj<size;jj++){
            if(path[ii][jj]==1){
            s+=abs(i-ii)+abs(j-jj);    
            }    
            }
        }best_value=min(best_value,s);//选取遍历得到的最小值即可 
    }
}
}
cout<<best_value<<endl;
} 

}
}

 

　　

推荐阅读