建物流中转站

记录所有的空地位置和每行每列房子的个数，然后遍历空地，计算其到所有行和列房子的距离，选择出最小的就行

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

/*

大致思路就是建立一个辅助数组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;
        }
        
    }

}