C 解法, 执行用时: 2ms, 内存消耗: 220KB, 提交时间: 2020-07-30

#include <stdio.h>
#include <stdlib.h>

int range(int p[100][100],int x, int y,int n)
{
   // p=(int *)malloc(sizeof(int)*n*n);
    int range_sum=0;
    for (int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(p[i][j]==1)
            range_sum+=(abs(x-i)+abs(y-j));
        }
    }
   // free(p);
    return range_sum;
}


/*
int main()
{
    int N;
    float x=0;
    float y=0;
    int count;
    scanf("%d",&N);
    int data[100][100];
   for(int i=0;i<N;i++)
    {  for(int j=0;j<N;j++)
        {
            scanf("%d",&data[i][j]);
            if(data[i][j]==1)
            {
                x+=i;
                y+=j;
                count++;
            }
        }
    }

   x = x / count;
    y = y / count;
    int range_1;
    int range_2;
    int range_3;
    range_1=range(data,x,y,N);
    range_2=range(data,x+1,y+1,N);
    range_3=range_1<range_2? range_1:range_2;
   // int range_1=range(data,x,y,N);
    //printf("%d",range(data,x, y,N)>range(data,x+1,y+1,N)?range(data,x+1,y+1,N):range(data,x,y,N));
        printf("%d",range_3);
    return 0;
}*/
///*
int Outcome(int Array[][100],int N,int x,int y)
{
    int i,j,way = 0;
       
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            if(Array[i][j] == 1)
            {
                way += abs(x - i);
                way += abs(y - j);
            }
        }
    }
   
    return way;
}
   
int main()
{
    float x,y;
    int N,i,j,X,Y,count = 0;
    int Array[100][100];
    int way,way1,way2;
    scanf("%d",&N);
   /* for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            scanf("%d",&Array[i][j]);
            if(Array[i][j] == 1)
            {
                x += i;
                y += j;
                count++;
            }
        }
    }*/
       for(int i=0;i<N;i++)
    {  for(int j=0;j<N;j++)
        {
            scanf("%d",&Array[i][j]);
            if(Array[i][j]==1)
            {
                x+=i;
                y+=j;
                count++;
            }
        }
    }
    if(count == 0)
    {
        printf("-1\n");
        return 0;
    }
    x = x / count;
    y = y / count;
    //way1 = Outcome(Array,N,x,y);
   // way2 = Outcome(Array,N,x+1,y+1);
       way1 = range(Array,x,y,N);
      way2 = range(Array,x+1,y+1,N);
    way = way1<way2?way1:way2;
    printf("%d",way);
       
    return 0;
}//*/

C++14 解法, 执行用时: 2ms, 内存消耗: 268KB, 提交时间: 2020-07-14

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>


int calDistance(int** arr, int n, int x, int y)
{
    int distance = 0, maxDistance = n * 2, sumDistance = 0, realX, realY;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (arr[i][j] == 0)
            {
                // 逼近理想距离
                distance = abs(x - i) + abs(y - j);
                if (distance < maxDistance)
                {
                    maxDistance = distance;
                    realX = i;
                    realY = j;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (arr[i][j] == 1)
            {
                sumDistance += (abs(realX - j) + abs(realY - i));
            }
        }
    }

    return sumDistance;
}

int main()
{
    int n, count = 0, result = -1, x = 0, y = 0;
    scanf("%d", &n);
    int** arr = (int **)malloc(n * sizeof(void *));
    for (int i = 0; i < n; ++i)
    {
        arr[i] = (int*)malloc(sizeof(int) * n);
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 1)
            {
                x += j;
                y += i;
                ++count;
            }
        }
    }

    if (count < n * n)
    {
        // 计算理想的中心坐标
        x /= count;
        y /= count;

        // 计算距离和
        result = calDistance(arr, n, x, y);
        int tmp = calDistance(arr, n, x + 1, y + 1);
        if (result > tmp)
        {
            result = tmp;
        }
    }

    for (int i = 0; i < n; ++i)
    {
        free(arr[i]);
    }
    free(arr);

    printf("%d", result);

    return 0;
}