建物流中转站 DP O(n^2)

• 行列分开算
• 每当中转站向右（下）移动一列（行），其他房子到中转站得行（列）距离变化为:
  1. 当前列（行）左边的房子距离+1
  2. 当前列（行）右边的房子距离-1
• 设第i列（行）左边的房子数 a_i,总房子数为sum
  1. 左边距离变化：+1 * a_i
  2. 右边距离变化：-1 * (sum-a_i)
  3. 总变化：-sum + 2*a_i
• 求出初始值（其他房子到第1行的行距离，到第1列的列距离），动态规划即可

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[][] g = new int[n][n];
        int[] row = new int[n];
        int[] col = new int[n];
        int sum = 0,disi = 0,disj = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int cur = sc.nextInt();
                if(cur==1){
                    sum++;row[i]++;col[j]++;
                    disi += i;
                    disj += j;
                }
                g[i][j] = cur;
            }
        }                             
        for(int i=1; i<n; i++){
            row[i] += row[i-1];
            col[i] += col[i-1];
        }
        int min = Integer.MAX_VALUE;
        int[][][] dp = new int[n][n][2];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==0 && j==0){
                    dp[i][j][0] = disi;
                    dp[i][j][1] = disj;
                }else{
                    dp[i][j][0] = i==0?disi:(dp[i-1][j][0]-sum+2*row[i-1]);
                    dp[i][j][1] = j==0?disj:(dp[i][j-1][1]-sum+2*col[j-1]);
                }
                if(g[i][j]==0){
                    min = Math.min(min,dp[i][j][0]+dp[i][j][1]); 
                }
            }
        }
        if(min==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(min);
    }
}