题解 | #建物流中转站#

#include <iostream>
#include <vector>
using namespace std;

int calDistance(vector<vector<int>>& grid, int n, int x, int y) {
    int minDist = n * 2;
    int bestX = 0, bestY = 0;
    
    // 找到距离重心最近的空地
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(grid[i][j] == 0) {
                int dist = abs(x - i) + abs(y - j);
                if(dist < minDist) {
                    minDist = dist;
                    bestX = i;
                    bestY = j;
                }
            }
        }
    }
    
    // 计算到所有房子的距离和
    int sumDist = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(grid[i][j] == 1) {
                sumDist += abs(bestX - i) + abs(bestY - j);
            }
        }
    }
    
    return sumDist;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    
    int count = 0, sumX = 0, sumY = 0;
    
    // 读入网格并计算重心
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if(grid[i][j] == 1) {
                sumX += i;
                sumY += j;
                count++;
            }
        }
    }
    
    // 如果全是房子，无法建站
    if(count == n * n) {
        cout << -1 << endl;
        return 0;
    }
    
    // 计算重心坐标
    int centerX = sumX / count;
    int centerY = sumY / count;
    
    // 计算最小距离和
    int result = calDistance(grid, n, centerX, centerY);
    result = min(result, calDistance(grid, n, centerX + 1, centerY + 1));
    
    cout << result << endl;
    return 0;
}

import java.util.*;

public class Main {
    static int calDistance(int[][] grid, int n, int x, int y) {
        int minDist = n * 2;
        int bestX = 0, bestY = 0;
        
        // 找到最近的空地
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 0) {
                    int dist = Math.abs(x - i) + Math.abs(y - j);
                    if(dist < minDist) {
                        minDist = dist;
                        bestX = i;
                        bestY = j;
                    }
                }
            }
        }
        
        // 计算总距离
        int sumDist = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    sumDist += Math.abs(bestX - i) + Math.abs(bestY - j);
                }
            }
        }
        
        return sumDist;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] grid = new int[n][n];
        
        int count = 0, sumX = 0, sumY = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
                if(grid[i][j] == 1) {
                    sumX += i;
                    sumY += j;
                    count++;
                }
            }
        }
        
        if(count == n * n) {
            System.out.println(-1);
            return;
        }
        
        int centerX = sumX / count;
        int centerY = sumY / count;
        
        int result = calDistance(grid, n, centerX, centerY);
        result = Math.min(result, calDistance(grid, n, centerX + 1, centerY + 1));
        
        System.out.println(result);
    }
}

def cal_distance(grid, n, x, y):
    min_dist = n * 2
    best_x = best_y = 0
    
    # 找到最近的空地
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                dist = abs(x - i) + abs(y - j)
                if dist < min_dist:
                    min_dist = dist
                    best_x, best_y = i, j
    
    # 计算总距离
    sum_dist = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                sum_dist += abs(best_x - i) + abs(best_y - j)
    
    return sum_dist

n = int(input())
grid = []
count = sum_x = sum_y = 0

# 读入网格并计算重心
for i in range(n):
    row = list(map(int, input().split()))
    grid.append(row)
    for j in range(n):
        if row[j] == 1:
            sum_x += i
            sum_y += j
            count += 1

if count == n * n:
    print(-1)
else:
    center_x = sum_x // count
    center_y = sum_y // count
    
    result = cal_distance(grid, n, center_x, center_y)
    result = min(result, cal_distance(grid, n, center_x + 1, center_y + 1))
    
    print(result)