c - 二维数组中的意外输出

Question

这个问题已经有答案了:

Maximum hourglass sum possible in a 6*6 array (3 个回答)

已关闭 3 年前。

给定一个 6x6 2D 数组:

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

我们将沙漏定义为值的子集，在此图形表示中索引落在该模式中:

a b c
  d
e f g

arr中有16个沙漏，沙漏总和是沙漏值的总和。计算arr中每个沙漏的沙漏总和，然后打印最大沙漏总和。

例如，给定二维数组:

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

我们计算以下 16 个沙漏值:

-63, -34, -9, 12, 
-10, 0, 28, 23, 
-27, -11, -2, 10, 
 9, 17, 25, 18

这是我写的代码

#include<stdio.h>

const int M=6;
const int N=6;

int hourglassSum(int arr_rows, int arr_columns, int arr[M][N]) {
    int rows,columns;
    rows=arr_rows-(arr_rows/3);
    columns=arr_columns-(arr_columns/3);
    int a[columns-1][rows-1];
    int min_r,min_c,max_r,max_c,sum;
    sum=0;
    for(int k=0;k<columns;k++)
    {
        min_c=k;
        max_c=k+2;
        for(int l=0;l<rows;l++)
        {
            min_r=l;
            max_r=l+2;
            sum=0;
            for(int i=min_c;i<=max_c;i++)
            {
                if(max_c>=arr_columns)
                    break;
                for(int j=min_r;j<=max_r;j++)
                {
                    if(max_r>=arr_rows)
                        break;
                    if(i!=min_c && i!=max_c)
                    {
                        int no=j+1;
                        sum +=arr[i][no];
                        break;
                    }
                    sum += arr[i][j];
                }
            }
            a[min_c][min_r]=sum;
        }
    }
    int max=-111;
    for(int b=0;b<columns;b++)
    {
        for(int c=0;c<rows;c++)
        {
            if(max<a[b][c])
                max=a[b][c];
        }
    }
    for(int i=0;i<columns;i++)
    {
        for(int j=0;j<rows;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    return max;

}

int main()
{
    int arr[6][6];
    int arr_rows=6;
    int arr_columns=6;
    for(int i=0;i<arr_columns;i++)
        for(int j=0;j<arr_rows;j++)
            scanf("%d",&arr[i][j]);
    int result=hourglassSum(arr_rows,arr_columns,arr);
    printf("\n%d",result);
}

我输入的内容为

-9 -9 -9 1 1 1
 0 -9 0 4 3 2
-9 -9 -9 1 2 3
 0 0 8 6 6 0
 0 0 0 -2 0 0
 0 0 1 2 4 0

预期输出是

-63 -34 -9 12
-10 0 28 23 
-27 -11 -2 10
9 17 25 18

但我的输出是

-63 -34 -9 -10
-10 0 28 -27
-27 -11 -2 9
9 17 25 18

出了什么问题？

Answer 1

您的计算:

rows=arr_rows-(arr_rows/3);
columns=arr_columns-(arr_columns/3);

恰好产生了正确的答案，因为 6/3 是 2，这是要减去的正确值。如果矩阵是 12x12，您将省略行和列 - 由于沙漏的形状，您应该减去 2(或减去 hourglass_width - 1 和 hourglass_height - 1) > 对于非方形沙漏的一般情况)。

使用 int max=-111; 是危险的 - 同样，它恰好适用于示例数据，但它不是通用解决方案。使用a[0][0]中的值作为初始最大值。它可能是一个幸运的猜测，实际上是最大值，但如果有的话，它会被另一个更大的值替换。

您应该消除 M 和 N 并使用:

int hourglassSum(int arr_rows, int arr_columns, int arr[arr_rows][arr_columns]) {

这将允许您将其他大小的数组传递给代码。

但是，主要问题是您将 a 矩阵设置得太小。您应该使用int a[columns][rows]。 (C 中的数组通常为 a[rows][columns]，但如果你保持一致，则可以反转它们，并且当 rows == columns 时差异并不重要> 无论如何。)通过尺寸较小的矩阵，我得到了你得到的结果；使用正确大小的矩阵，我得到了预期的结果。

#include <stdio.h>

static int hourglassSum(int arr_rows, int arr_columns, int arr[arr_rows][arr_columns])
{
    int rows = arr_rows - 2;
    int columns = arr_columns - 2;
    int a[columns][rows];

    for (int k = 0; k < columns; k++)
    {
        int min_c = k;
        int max_c = k + 2;
        for (int l = 0; l < rows; l++)
        {
            int min_r = l;
            int max_r = l + 2;
            int sum = 0;
            for (int i = min_c; i <= max_c; i++)
            {
                if (max_c >= arr_columns)
                    break;
                for (int j = min_r; j <= max_r; j++)
                {
                    if (max_r >= arr_rows)
                        break;
                    if (i != min_c && i != max_c)
                    {
                        int no = j + 1;
                        sum += arr[i][no];
                        break;
                    }
                    sum += arr[i][j];
                }
            }
            a[k][l] = sum;
        }
    }
    int max = a[0][0];
    for (int b = 0; b < columns; b++)
    {
        for (int c = 0; c < rows; c++)
        {
            if (max < a[b][c])
                max = a[b][c];
        }
    }
    for (int i = 0; i < columns; i++)
    {
        for (int j = 0; j < rows; j++)
            printf(" %3d", a[i][j]);
        printf("\n");
    }
    return max;
}

int main(void)
{
    int arr[6][6];
    int arr_rows = 6;
    int arr_columns = 6;
    for (int i = 0; i < arr_columns; i++)
    {
        for (int j = 0; j < arr_rows; j++)
        {
            if (scanf("%d", &arr[i][j]) != 1)
            {
                fprintf(stderr, "failed to read an integer\n");
                return 1;
            }
        }
    }

    int result = hourglassSum(arr_rows, arr_columns, arr);
    printf("\n%d\n", result);
    return 0;
}

输出:

 -63 -34  -9  12
 -10   0  28  23
 -27 -11  -2  10
   9  17  25  18

28

请注意，这或多或少是对问题中代码的最小修复。我自己的代码在很多方面看起来都会有所不同(不同的变量名、更多的函数等)。另一项更改(上面未进行):您实际上不需要数组 a；您可以在计算每个位置的沙漏总和后简单地记录当前最大值。

对于alternative input :

-1  1 -1  0  0  0
 0 -1  0  0  0  0
-1 -1 -1  0  0  0
 0 -9  2 -4 -4  0
-7  0  0 -2  0  0
 0  0 -1 -2 -4  0

我得到输出:

  -5  -2  -2   0
  -9 -13  -6  -8
 -19  -2  -7  -6
  -8 -14 -15 -14

0

这会产生您所说的预期答案0(并且我同意0是应该预期的)。