首页 > 试题广场 >

建物流中转站

[编程题]建物流中转站
  • 热度指数:8686 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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
// 所有1点到达某个0点(x,y)的距离和 = 每行1点的数量 * 行间距 + 每列1点的数量 * 列间距
// 所以我们只需分别记录每行和每列1的数量和所有0点的坐标即可
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

int main(){
    int n;
    cin >> n;
    //分别存储每行的1和每列的1数量
    vector<vector<int> > cnts(2, vector<int> (n, 0)); 
    //候选点(0点)的坐标
    vector<pair<int, int> > points;
    int cnt, temp;
    for(int i = 0; i<n; ++i){
        for(int j = 0; j<n; ++j){
            cin >> temp;
            //记录每行和每列的1的数量
            if(temp) {
                ++cnts[0][i];
                ++cnts[1][j];
            }
            else{
                //将0点的坐标记录到points中
                points.push_back(make_pair(i, j));
            }
        }
    }
    if(points.empty()){
        cout << -1 << endl;
    }
    else{
        //计算每个0坐标的距离和,得到最大值
        int min = numeric_limits<int>::max(), cur_dist;
        for(auto pnt : points){
            cur_dist = 0;
            //pnt.first横坐标,对应其他行的1之和,表示纵向路径和
            //pnt.second纵坐标,对应其他列的1之和,表示横向路径和
            for(int i = 0; i<n; ++i){
                if(i!=pnt.first) cur_dist += abs(i-pnt.first)*cnts[0][i];
                if(i!=pnt.second) cur_dist += abs(i-pnt.second)*cnts[1][i];
            }
            if(cur_dist<min) min = cur_dist;
        }
        cout << min << endl;
    }
    return 0;
}



编辑于 2020-07-27 14:23:36 回复(1)
#include <bits/stdc++.h>
using namespace std;

struct P{
    int x,y;
};

int main(){
    int n;
    cin>>n;
    int G[n][n];
    vector<P> a,b;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            cin>>G[i][j];
            if(G[i][j]==1)
                a.push_back(P{i,j});
            else
                b.push_back(P{i,j});
        }
    
    if(b.size()==0)
        cout<<-1<<endl;
    else{
        int Min=INT_MAX;
        for(int i=0;i<b.size();i++){
            int s = 0;
            for(int j=0;j<a.size();j++)
                s += abs(a[j].x-b[i].x) + abs(a[j].y-b[i].y);
            Min = min(Min, s);
        }
        cout<<Min<<endl;
    }
    return 0;
}

发表于 2019-11-27 00:38:55 回复(0)
n^2 做法
二维变一维
先计算x轴上每个点的贡献
然后先计算y轴上每个点的贡献
最后计算每个所有点的贡献,求出最小值。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<bits/stdc++.h>
using namespace std;
int z[1005][1005];
int x[1005];
int y[1005];
int vx[1005],vy[1005];
int main()
{
  //  freopen("in","r",stdin);
    int n;
    cin>>n;
    int t;
    int sum=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>z[i][j];
            if(z[i][j]==1){
                x[i]++;
                y[j]++;
                sum++;
            }
        }
    }
    int sumx=0;
    int numx=0;
    for(int i=0;i<n;i++){
        numx+=(x[i]*(i+1));
    }
    for(int i=0;i<n;i++){
        numx-=(sum-sumx);
        numx+=sumx;
        vx[i]=numx;
        sumx+=x[i];
       // cout<<vx[i]<<' '<<numx<<' '<<sumx<<endl;
    }
    int sumy=0;
    int numy=0;
    for(int i=0;i<n;i++){
        numy+=(y[i]*(i+1));
    }
    for(int i=0;i<n;i++){
        numy-=(sum-sumy);
        numy+=sumy;
        vy[i]=numy;
        sumy+=y[i];
    }

    int maxn=100000000;
    for(int i=0;i<n;i++ ){
        for(int j=0;j<n;j++){
            if(z[i][j]==0){
                //cout<<vx[i]+vy[j]<<endl;
                maxn=min(maxn,vx[i]+vy[j]);
            }
        }
    }
    if(maxn==100000000)
    cout<<-1<<endl;
    else cout<<maxn<<endl;
    return 0;
}
发表于 2019-06-29 16:27:08 回复(0)
def cal_distance(matrix, x_center, y_center):
    real_x_center, real_y_center = 0, 0
    max_distance = n * 2  # 矩阵两点间的最大距离
    for i in range(n):  # 求在理想中心点附近最近的真实中心点
        for j in range(n):
            if matrix[i][j] == 0:  # 当点空时
                temp_distance = abs(x_center - i) + abs(y_center - j)
                if temp_distance < max_distance:  # 替换最大距离
                    max_distance = temp_distance
                    real_x_center, real_y_center = i, j  # 替换真实中心点坐标
    distance_sum = 0
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 1:  # 当点有房屋时
                distance_sum += abs(real_x_center - i) + abs(real_y_center - j)  # 计算距离总和
    return distance_sum


n = int(input())

matrix = [list(map(int, input().split())) for i in range(n)]

x_sum = 0
y_sum = 0
total_house_count = 0
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 1:
            x_sum += i
            y_sum += j
            total_house_count += 1
if total_house_count == n * n:
    print(-1)
else:
    x_center = x_sum / total_house_count  # 利用平均值计算出理想中心点
    y_center = y_sum / total_house_count
    print(cal_distance(matrix, x_center, y_center))
编辑于 2019-08-03 10:25:16 回复(0)
//Optimize algorithm by seting poles
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x3f3f3f3f;

int main(){
    
    int n;
    cin>>n;
    vector<vector<int>>    grid( n, vector<int>(n,0) );
    vector<pair<int,int>>    vec;
    //set limits xl,xr,yu,yd
    int xl=n-1,xr=0,yu=n-1,yd=0;
    for(int i=0;i<n;++i){    
        for(int j=0,tmp;j<n;++j){
            cin>>tmp;
            if(tmp){
                grid[i][j]=1;
                vec.push_back(make_pair(i,j));
                if( i<yu)    yu=i;
                if( i>yd)    yd=i;
                if( j<xl)    xl=j;
                if( j>xr)    xr=j;
            }
        }
    }
    //if all elements in the area limited by xl,xr.yu,yd is 1, the solution is outside it
    yu = max(yu-1, 0);
    yd = min(yd+1, n-1);
    xl = max(xl-1 , 0);
    xr = min(xr+1, n-1);
    
    int sum, minlen= inf;
    for(int u=yu ; u<=yd ; ++u ){
        for(int l=xl ; l<=xr; ++l ){
            if( grid[u][l]==0 ){
                sum=0;
                for(int i=0;i<vec.size();++i){
                    sum += abs( vec[i].first-u ) + abs( vec[i].second - l );
                }
                minlen = min(minlen, sum);
            }    
        }
            
    }
    if(minlen<inf)    cout<<minlen;
    else cout<<-1;
            
    return 0;
}

发表于 2019-07-24 11:24:40 回复(0)
记录所有的空地位置和每行每列房子的个数,然后遍历空地,计算其到所有行和列房子的距离,选择出最小的就行
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] grid = new int[n][n];
        int[][] onesCnt = new int[2][n];    // 第一行是每行1的个数,第二行是每列1的个数
        ArrayList<int[]> startPoints = new ArrayList<>();
        for(int i = 0; i < n; i++){
            String[] row = br.readLine().split(" ");
            for(int j = 0; j < n; j++){
                int val = Integer.parseInt(row[j]);
                if(val == 1){
                    onesCnt[0][i] ++;
                    onesCnt[1][j] ++;
                }else{
                    startPoints.add(new int[]{i, j});
                }
            }
        }
        // 没有空地直接返回-1
        if(startPoints.isEmpty()){
            System.out.println(-1);
        }else{
            int minDis = Integer.MAX_VALUE;
            for(int[] point: startPoints){      // 以当前位置为中转站位置
                int curDis = 0;
                for(int i = 0; i < n; i++){
                    curDis += Math.abs(i - point[0]) * onesCnt[0][i];     // 距离为abs(i-point[0])的点有onesCnt[0][i]个
                    curDis += Math.abs(i - point[1]) * onesCnt[1][i];
                }
                minDis = Math.min(minDis, curDis);
            }
            System.out.println(minDis);
        }
    }
}
scala版
import scala.io.StdIn
import scala.collection.mutable.ListBuffer

object Main {
    def main(args: Array[String]): Unit = {
        val n = StdIn.readInt
        val freeSpace = ListBuffer[Array[Int]]()
        val onesCnt = Array.ofDim[Int](2, n)
        for(i <- 0 until n){
            val row = StdIn.readLine.split(" ")
            for(j <- 0 until n){
                if(row(j) == "1"){
                    onesCnt(0)(i) += 1
                    onesCnt(1)(j) += 1
                }else
                    freeSpace.append(Array[Int](i, j))
            }
        }
        if(freeSpace.isEmpty){
            println(-1)
        }else{
            var minDis = Integer.MAX_VALUE
            for(pos: Array[Int] <- freeSpace){
                var curDis = 0
                for(i <- 0 until n)
                    curDis += math.abs(i - pos(0)) * onesCnt(0)(i) + math.abs(i - pos(1)) * onesCnt(1)(i)
                minDis = math.min(minDis, curDis)
            }
            println(minDis)
        }
    }
}

编辑于 2021-09-08 16:23:41 回复(0)
注意距离只需要x坐标之差+y坐标之差即可,当时还犹豫了下是不是开根号求距离,看了下题解才知道直接abs即可
#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#include<limits.h>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    queue<pair<int,int>> emp;
    queue<pair<int,int>> house;
    for(int i=0;i<n;++i) {
        for(int j=0;j<n;++j) {
            int x;
            cin>>x;
            if(x==1) {
                house.push(pair<int,int>(i,j));
            } else {
                emp.push(pair<int,int>(i,j));
            }
        }
    }
    if(emp.size()==0) {
        cout<<"-1"<<endl;
        return 0;
    }
    int ans=INT_MAX;
    while(!emp.empty()) {
        auto [x,y]=emp.front(); emp.pop();
        int count=0;
        for(int i=house.size();i>0;--i) {
            auto [a,b]=house.front(); house.pop();
            count+=abs(a-x)+abs(b-y);
            house.push(pair<int,int>(a,b));
        }
        ans=min(ans,count);
    }
    cout<<ans<<endl;
    return 0;
}


发表于 2021-07-04 17:29:54 回复(0)
package main

import (
	"fmt"
	"math"
)

func juli(x1, y1, x2, y2 int) int { //  输入两个点的横纵坐标,返回两个点的距离
	num_x, num_y := 0, 0
	if x1 > x2 {
		num_x = x1 - x2
	} else {
		num_x = x2 - x1
	}
	if y1 > y2 {
		num_y = y1 - y2
	} else {
		num_y = y2 - y1
	}
	num := num_x + num_y
	return num
}

// 思路 : 在输入 时, 把 0 的横纵坐标 存入一个二维数组, 1 的存入一个二维数组,
// 0 的 那个数组挨个取出 横纵坐标, 和 1 的所有横纵坐标 求距离 , 距离相加
func main() {
	N := 0
	_, _ = fmt.Scan(&N)
	num_list1 := [][]int{}
	num_list0 := [][]int{}
	num_1 := 0 // 1的数量
	u := 0
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			_, _ = fmt.Scan(&u)
			if u == 1 {
				num_1 += 1
				num_list1 = append(num_list1, []int{i, j})
			} else {
				num_list0 = append(num_list0, []int{i, j})

			}
		}
	}
	if num_1 == N*N {
		fmt.Println(-1)
		return
	}

	sum := 0
	min := math.MaxInt64
	for i := 0; i < len(num_list0); i++ {
		for j := 0; j < len(num_list1); j++ {
			sum += juli(num_list0[i][0], num_list0[i][1], num_list1[j][0], num_list1[j][1])
		}
		if sum < min {
			min = sum
		}
		sum = 0
	}
	fmt.Println(min)
}

发表于 2020-06-24 21:22:02 回复(0)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Arrays;
class Point{
    private int x;
    private int y;
    public Point(){}
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    public void setX(int x){
        this.x = x;
    }
    public void setY(int y){
        this.y = y;
    }
    public int getX(){
        return this.x;
    }
    public int getY(){
        return this.y;
    }
    public int getDistance(Point p){
        return Math.abs(this.x - p.x) + Math.abs(this.y - p.y);
    }
    public static Object findMin(Object[] nums){
        Arrays.sort(nums);
        return nums[0];
    }
}
public class Main{
    public static Boolean isBuild(int[][] nums){
        int i,j;
        for(i = 0 ; i < nums.length ; i ++){
            for(j = 0 ; j < nums[i].length ; j ++){
                if(nums[i][j] == 0){
                    return true;
                }
            }
        }
        return false;
    }
    public static int getMin(int[][] nums){
        int i;
        int j;
        int sum;
        ArrayList<Point> stations = new ArrayList<Point>();
        ArrayList<Point> houses = new ArrayList<Point>();
        ArrayList<Integer> distances = new ArrayList<Integer>();
        if(isBuild(nums) == true){
            for(i = 0 ; i < nums.length ; i ++){
                for( j = 0 ; j < nums[i].length ; j ++){
                    if(nums[i][j] == 0){
                        stations.add(new Point(i,j));
                    }else if(nums[i][j] == 1){
                        houses.add(new Point(i,j));
                    }
                }
            }
            for(i = 0 ; i < stations.size() ; i ++){
                sum = 0;
                for(j = 0; j < houses.size() ; j ++){
                    sum += stations.get(i).getDistance(houses.get(j));
                }
                distances.add(sum);
            }
            int tempNum =Integer.parseInt(Point.findMin(distances.toArray()).toString());
            return tempNum;
        }
        return -1;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] nums = new int[n][];
        for(int i = 0 ; i < n ; i ++){
            nums[i] = new int[n];
            for(int j = 0 ; j < n ; j ++){
                nums[i][j] = scan.nextInt();
            }
        }
        int result = getMin(nums);
        System.out.println(result);
    }
}
发表于 2020-05-27 11:19:06 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n = 0;
	int flag = INT_MAX;
	int sum = 0;
	int itmp = INT_MAX;
	cin >> n;
	vector<vector<int> > arr(n, vector<int> (n, 0));
	vector<pair<int, int> > arr2;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (0 == arr[i][j]) {
				flag = 0;//是否能够修建标准位,0不能,1能
				arr2.push_back(make_pair(i, j));//记录0的位置
			}
		}
	}
	if (0 != flag) {
		cout << "-1" << endl;
		return 0;
	}

	vector<pair<int, int> >::iterator it = arr2.begin();
	while (it != arr2.end()) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (1 == arr[i][j]) {
					//计算每个0点的修建距离和
					sum += (abs(i - (*it).first) + abs(j - (*it).second));
				}
			}
		}
		if (sum < itmp) {
			//得到最小距离和
			itmp = sum;
		}
		sum = 0;
		//下一个0点
		it++;
	}

	cout << itmp << endl;

	return 0;
}

发表于 2019-08-20 16:51:41 回复(0)
/*
大致思路就是建立一个辅助数组result[n][n] 表示每个点的结果。
main方法遍历数组,
若[i][j]为1,result[i][j]设为Integer MAX再调用findZero方法 从i,j开始往后寻找0并计算距离结果累加放入result[i][j].
若[i][j]为0就调用finOne方法从i,j开始往后寻找1并计算距离累加都放入放入起点处的result[i][j].
main方法的2层循环结束,再从result中找最小的.
*/

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [][] q = new int[n][n];                                     //问题数组
        int [][] result = new int[n][n];                              //结果数组
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                q[i][j] = sc.nextInt();
                result[i][j] = 0;
            }
        }
        sc.close();
        
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                if(q[i][j] == 0){
                    findOne(q, result, i, j, n);                             //碰到0就往后面找1
                }else{
                    result[i][j] = Integer.MAX_VALUE;
                    findZero(q, result,i, j, n);                              //否则就找0
                }
            }
        }
        
        int minResult = Integer.MAX_VALUE;
        
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                if(result[i][j] < minResult){
                    minResult = result[i][j];
                }
            }
        }
        minResult = minResult == Integer.MAX_VALUE ? -1: minResult;
        System.out.println(minResult);
    }

    private static void findZero(int[][] q, int[][] result, int x, int y, int n) {
        int j = y;
        for(int i=x; i < n; i++){
            for(; j < n; j++){
                if(q[i][j] == 0){
                    result[i][j] += (Math.abs(i - x) + Math.abs(j - y));   //把距离分散到碰到的0上面
                }
            }
            j = 0;
        }

        
    }

    private static void findOne(int[][] q, int[][] result, int x, int y, int n) {
        int j = y;
        for(int i=x; i < n; i++){
            for(; j < n; j++){
                if(q[i][j] == 1){
                    result[x][y] += (Math.abs(i - x) + Math.abs(j - y)); //把距离累加到 result[x][y]上
                }
            }
            j = 0;
        }
        
    }

}

发表于 2019-08-01 17:56:24 回复(0)
//记录房子坐标点,计算每个空地的距离值,记录最小值
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[][] matrix = new int[n][n];
            ArrayList<int[][]> al = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = sc.nextInt();
                    if(matrix[i][j]==1){
                       int[][] xy = new int[1][2];
                       xy[0][0]=i;
                       xy[0][1]=j;
                       al.add(xy);
                    }
                }
            }
            int res = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int temp=0;
                    if(matrix[i][j]==0){
                        for (int k = 0; k < al.size(); k++) {
                            temp+=Math.abs(al.get(k)[0][0]-i)+Math.abs(al.get(k)[0][1]-j);
                        }
                        res = res>temp?temp:res;
                    }
                }
            }
            System.out.println(res==Integer.MAX_VALUE?-1:res);
        }
    }
}

发表于 2019-11-05 20:22:55 回复(1)
#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
};
int main()
{
    int n,sum=0,minn=INT_MAX;cin>>n;
    vector<node> fang,di;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            int t;cin>>t;node p;
            p.x=i;p.y=j;
            if(t)    fang.push_back(p);
            else    di.push_back(p);
        }
    if(di.empty())    {cout<<-1<<endl;return 0;}
    for(int i=0;i<di.size();i++)
    {
        sum=0;
        for(int j=0;j<fang.size();j++)
            sum+=abs(fang[j].x-di[i].x)+abs(fang[j].y-di[i].y);
        minn=min(minn,sum);
    }
    cout<<minn<<endl;
}
简单易懂。
发表于 2022-01-17 05:19:36 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        // 空间复杂度 O(2n),时间复杂度O(n*n)
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count1=0;
        int[][] tem1 = new int[n*n][2];//储存 数组值 =1的位置
        int count2=0;
        int[][] tem2 = new int[n*n][2];//储存 数组值 =0的位置
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int a= sc.nextInt();
                if(a==0) {
                    tem2[count2][0]=i;
                    tem2[count2][1]=j;
                    count2++;
                }
                if(a==1) {
                    tem1[count1][0]=i;
                    tem1[count1][1]=j;
                    count1++;
                }
            }
        }
        if(count1==0) {System.out.println(0);return;}
        if(count2==0){System.out.println(-1);return;}
        int min=0;
        for(int i=0;i<count2;i++){//数组值 =0的位置
            int tem=0;
            for(int j=0;j<count1;j++){//数组值 =1的位置
                tem += Math.abs(tem2[i][0]-tem1[j][0])+Math.abs(tem2[i][1]-tem1[j][1]);
            }
            if(i==0) min=tem;
            else
            min = Math.min(min,tem);
        }
        System.out.println(min);
        
    }
}
发表于 2022-01-08 14:32:46 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        List<Data> list0 = new ArrayList<>();
        List<Data> list1 = new ArrayList<>();

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int num = in.nextInt();
                if(num==0){
                    list0.add(new Data(i,j));
                }else{
                    list1.add(new Data(i,j));
                }
            }
        }

        if(list0.size()==0){
            System.out.println(-1);
            return;
        }

        int count=0;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<list0.size();i++){
            for(int j=0;j<list1.size();j++){
                count += (Math.abs(list0.get(i).x-list1.get(j).x)
                        +Math.abs(list0.get(i).y-list1.get(j).y));
            }
            if(count<min){
                min = count;
            }
            count=0;
        }
        System.out.println(min);
    }

    static class Data{
        public int x,y;

        public Data(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

发表于 2021-08-06 11:21:31 回复(0)
//抄的题解里面的,保存一下为了记录一下自己的输入输出处理没问题😂😂😂

#include <vector>
#include <iostream>
#include <limits.h>
#include <algorithm>

using namespace std;

int main() {
    int n = 0;
    cin >> n;
    vector<vector<int>> num(2, vector<int>(n, 0));
    vector<pair<int, int>> points;
    int dist = INT_MAX;
    for (int i = 0; i < n; ++i) {
        int tmp = 0;
        int j = 0;
        while (cin >> tmp) {
            if (tmp == 1) {
                ++num[0][i];
                ++num[1][j];
                
            }
            else {
                points.push_back(make_pair(i, j));
            }
            ++j;
            if (cin.get() == '\n') break;
        }
    }
    if (points.empty()) {
        cout << -1 << endl;
    }
    for (auto point : points) {
        int curdist = 0;
        for (int i = 0; i < n; ++i) {
            if (point.first != i) curdist  = abs(i - point.first) * num[0][i] + curdist;
            if (point.second != i) curdist  = abs(i - point.second) * num[1][i] + curdist;
        }
        dist = min(dist, curdist);
    }
    cout << dist << endl;
    return 0;
发表于 2021-07-03 23:09:04 回复(0)
#include<bits/stdc++.h>

using namespace std;

int main(){
    int n = 0;
    cin >> n;
    vector<vector<int>> grid(n+1, vector<int>(n+1,0));
    int k = 0;
    int count = 0;
    //分别用来存放0或1的横纵坐标
    vector<int> pos_0_x;
    vector<int> pos_0_y;
    vector<int> pos_1_x;
    vector<int> pos_1_y;
    
    for( int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> grid[i][j];
            if( grid[i][j] == 1 ) {
                count++;
                pos_1_x.push_back(i);
                pos_1_y.push_back(j);
            }else if( grid[i][j] == 0 ){
                pos_0_x.push_back(i);
                pos_0_y.push_back(j);
            }
        }
    }
    if( count == n*n ) {
        cout << -1 <<endl;
        return 0;
    }
    if( pos_0_x.size() == 0 || pos_0_y.size() == 0 ){
        cout << -1 <<endl;
        return 0;
    }
    int min_dis = INT_MAX;
    
    for( int i = 0; i < pos_0_x.size(); i++ ){
        int min_x = 0, min_y = 0;
        for( int j = 0; j < pos_1_x.size(); j++  ){
            min_x += abs(pos_0_x[i] - pos_1_x[j]);
            min_y += abs(pos_0_y[i] - pos_1_y[j]);
        }
        min_dis = min( min_dis, min_x + min_y);
    }
    cout << min_dis << endl;
    
    return 0;
}
发表于 2020-07-30 15:27:33 回复(0)
自己小小改了下题,因为懒得手动输入0和1,就改成自动输入随机数(0,1),其他条件保持一致。
import random
a = input()
list1 = []
str1 = ''
list2 = []
for j in range(0,int(a)):
    for i in range(0,int(a)):
            if i != int(a)-1:
                b = random.randint(0,1)  #赋值b为当前的随机数
                str1 += str(b) + ' ' 
                list1.append('%d,%d,%d'%(i,j,b)) #给每个数赋予坐标提供后期算距离
            if i == int(a)-1:
                b = random.randint(0,1)
                str1 += str(b) #当一行数满足矩阵宽度时准备换行
                list1.append('%d,%d,%d'%(i,j,b))
                print(str1) #'打印并换行'
                str1 = ''
for i in list1:
    count = 0
    for j in list1:
        if int(i.split(',')[2]) == 0 and j != i and int(j.split(',')[2]) == 1:
                count += abs(int(i.split(',')[0])-int(j.split(',')[0])) + abs(int(i.split(',')[1])-int(j.split(',')[1]))
                #循环计算每个可选地址到其他地址的距离之和
    if count != 0:  
        list2.append(count)      #只收集有值的count            
list2.sort()
print(list2[0]) #取最小值
发表于 2020-07-28 16:49:24 回复(0)
n=int(input())
l=[]
yi=[]
ling=[]
count=0
min_val=100000000000000
foriinrange(n):
    line=list(map(int,input().split()))
    forjinrange(len(line)):
        ifline[j]==1:
            count+=1
            yi.append([i,j])
        ifline[j]==0:
            ling.append([i,j])
 
sum_val=0
forkinling:
    forhinyi:
        sum_val+=(abs(k[0]-h[0])+abs(k[1]-h[1]))
    min_val=min(sum_val,min_val)
    sum_val=0
ifcount==n*n:
    print(-1)
print(min_val)
发表于 2020-07-21 17:24:14 回复(0)
n = int(input())
a = [ list(map(int, input().split())) for i in range(n) ]

#理想最小
x_sum = 0
y_sum = 0
house_count = 0
for i in range(n):
    for j in range(n):
        if a[i][j] == 1:
            x_sum += i
            y_sum += j
            house_count += 1
x_cen = x_sum / house_count
y_cen = y_sum / house_count

#真实最小:和“理想最小”的diff最小
def real(n, a, x_cen, y_cen):
    diff = float('inf')
    diff_tem = 0
    x_real = 0
    y_real = 0
    for i in range(n):
        for j in range(n):
            if a[i][j] == 0:
                diff_tem = abs(i - x_cen) +abs(j-y_cen)
                if diff_tem < diff:
                    diff = diff_tem
                    x_real = i
                    y_real = j
    return x_real,y_real

if house_count == n * n:
    print(-1)
else:
    x_real,y_real = real(n, a, x_cen, y_cen)
    dis = 0
    for i in range(n):
        for j in range(n):
            if a[i][j] == 1:
                dis += abs(i-x_real) + abs(j-y_real)
    print(dis)
根据上面大佬们的思路,写了个py3的
发表于 2020-07-20 22:08:04 回复(0)