建物流中转站

#  二维前缀和
if __name__ == '__main__':
    n = int(input())
    l = []
    for _ in range(n):
        line = input()
        l.append(list(map(int, line.split())))
    
    dp = [[0 for _ in range(n)] for _ in range(n)]
    dp[0][0] = l[0][0]
    dist_init = 0
    ones = int(l[0][0] == 1)
    for i in range(1,n):
        if l[0][i] == 1:
            dist_init += i
            ones += 1
        if l[i][0] == 1:
            dist_init += i
            ones += 1
        dp[0][i] = dp[0][i-1] + l[0][i]
        dp[i][0] = dp[i-1][0] + l[i][0]
    for i in range(1,n):
        for j in range(1,n):
            if l[i][j] == 1:
                dist_init += i + j
                ones += 1
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + l[i][j]
    
    if ones == n:
        print(-1)
    
    res = dist_init
    dist = [[0 for _ in range(n)] for _ in range(n)]
    dist[0][0] = dist_init
    for i in range(1,n):
        dist[i][0] = dist[i-1][0] + dp[i-1][-1] - (ones - dp[i-1][-1])
        dist[0][i] = dist[0][i-1] + dp[-1][i-1] - (ones - dp[-1][i-1])
        if l[i][0] == 0 and dist[i][0] < res:
            res = dist[i][0]
        if l[0][i] == 0 and dist[0][i] < res:
            res = dist[0][i]
    for i in range(1,n):
        for j in range(1,n):
            dist[i][j] = dist[i-1][j] + dp[i-1][-1] - (ones - dp[i-1][-1])
            if l[i][j] == 0 and dist[i][j] < res:
                res = dist[i][j]
    print(res)

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