建物流中转站

// 所有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;
}

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;
}

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))

//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;
}

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)
}

#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;
}

#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;
}

//记录房子坐标点，计算每个空地的距离值，记录最小值
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);
        }
    }
}

#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;
}

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;
        }
    }
}

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)