-1

我在hackerearth 上阅读了一个问题,它要求我们打印螺旋矩阵 N N 的两条对角线的总和,其中 N 作为输入。a[0][0]=N N 的螺旋矩阵,中心为 1,即

16  15  14  13

5   4   3   12

6   1   2   11

7   8   9   10

我已经为此实现了代码,但是当输入 N >= 10^5 时会出现分段或运行时错误

我无法弄清楚发生了什么

#include <stdio.h>

int main(void) {
long long int n,test;
scanf("%lld",&test);
while(test--){
    scanf("%lld",&n);
    long long int p=n*n;
    long long int r1=0,r2=n-1,c1=0,c2=n-1,i,j;
    long long int a[n][n];
    while(p>=1)
    {
        for(i=c1;i<=c2;i++)
        {
            a[r1][i]=p--;
        }
        for(j=r1+1;j<=r2;j++)
        {
            a[j][c2]=p--;
        }
        for(i=c2-1;i>=c1;i--)
        {
            a[r2][i]=p--;
        }
        for(j=r2-1;j>=r1+1;j--)
        {
            a[j][c1]=p--;
        }
        c1++;
        c2--;
        r1++;
        r2--;
    }
    long long int sum=0;
       for ( i = 0, j =0; i< n && j < n; i++, j++) {
              sum = sum + a[i][j];

       }

       for ( i=0,j=n-1 ; i<n && j>=0 ; i++, j--) {
              sum= sum + a[i][j];

       }

           printf("%lld\n",sum%1000000009);


}
return 0;
}
4

1 回答 1

0

long long int a[n][n];如果 N >= 10^5,则太大而无法固定在堆栈中

用。。。来代替long long (*a)[n] = malloc(sizeof(long long [n][n]));


16  15  14  13

5   4   3   12

6   1   2   11

7   8   9   10

最后一个元素是 n * n : (4 * 4 = 16)
前角元素是最后一个元素 - (n - 1) : 16 - (4 - 1) = 16 - 3 = 13
前角元素: 13 - 3 = 10
pre pre pre 角元素:10 - 3 = 7
(4次)


一种不使用二维数组的方法。

#include <stdio.h>

int main(void){
    long long n;//The length of the side
    long long lastValue;//n*n
    long long sum = 0;

    scanf("%lld", &n);

    sum += (n & 1);//center (1) if odd, Not counting duplicates;

    while(n >= 2){
        lastValue = n * n;
        for(int i = 0; i < 4; ++i){//4 times
            sum += lastValue;
            lastValue -= n - 1;//pre lastValue..
        }
        n -= 2;
    }
    printf("Ans.%lld\n", sum);
    return 0;
}
于 2016-06-23T22:37:00.617 回答