Magic Square

Magic Square

时间： 1ms        内存：64M

描述：

In recreational mathematics, a magic square of n-degree is an arrangement of n2 numbers, distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. For example, the picture below shows a 3-degree magic square using the integers of 1 to 9.

Given a finished number square, we need you to judge whether it is a magic square.

输入：

The input contains multiple test cases.

The first line of each case stands an only integer N (0 < N < 10), indicating the degree of the number square and then N lines follows, with N positive integers in each line to describe the number square. All the numbers in the input do not exceed 1000. A case with N = 0 denotes the end of input, which should not be processed.

输出：

For each test case, print "Yes" if it's a magic square in a single line, otherwise print "No".

示例输入：

2
1 2
3 4
2
4 4
4 4
3
8 1 6
3 5 7
4 9 2
4
16 9 6 3
5 4 15 10
11 14 1 8
2 7 12 13
0

示例输出：

No
No
Yes
Yes

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
int cs(int a[],int n)
{
    int i,j;
    for(i=1;i<=n-1;i++)
    {
        for(j=i+1;j<=n;j++)
            if(a[i]==a[j])return 1;
    }
    return 0;
}
void pd(int sum[],int n)
{
    int s=sum[1],flag=0,i;
    for(i=1;i<=2*n+2;i++)
    {
        if(sum[i]!=s)flag=1;
    }
    if(flag==0) printf("Yes\n");
    else printf("No\n");
}
int main()
{
    int n,a[11][11],i,j,sum[50],s[121],k;
    while(scanf("%d",&n)&& n!=0)
    {
        if(n==1)
        {
            scanf("%d",&a[1][1]);
            printf("Yes\n");
            continue;
        }
        k=1;
        for(i=1;i<=50;i++)
            sum[i]=0;
        for(i=1;i<=n;i++)
        {
         for(j=1;j<=n;j++)
         {
             scanf("%d",&a[i][j]);
             s[k++]=a[i][j];
             sum[i]+=a[i][j];
             if(i==j)
             sum[2*n+1]+=a[i][j];
             if(i==n+1-j)
                sum[2*n+2]+=a[i][j];
         }
        }
        if(cs(s,n*n))
        {
            printf("No\n");
            continue;
        }
        for(j=1;j<=n;j++)
        for(i=1;i<=n;i++)
        sum[i+n]+=a[i][j];
        pd(sum,n);
    }
    return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<math.h>
int main()
{
    int n;
    int a[100][100],b[1005],c[50];
    int i,j,k;
    while(1)
    {
        scanf("%d",&n);
        if(n==0)
            break;
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
                b[a[i][j]]++;
            }
            for(i=0;i<1000;i++)
                if(b[i]>1)
                    break;
                if(i<1000)
                    printf("No\n");
                else
                {
                    int d1=0,d2=0;
                    for(i=0;i<n;i++)
                    {
                        d1+=a[i][i]; 
                        d2+=a[i][n-i-1];
                    }
                    for(i=0;i<n;i++)
                        for(j=0;j<n;j++)
                            c[i]+=a[i][j]; 
                    k=i; 
                    for(i=0;i<n;i++)
                    {
                       for(j=0;j<n;j++)
                         c[k]+=a[j][i]; 
                       k++;
                    }
                    if(d1!=d2)
                        printf("No\n"); 
                    else
                    {
                            for(i=0;i<k;i++)
                                if(c[i]!=d1)
                                    break;
                                if(i==k)
                                    printf("Yes\n");
                                else
                                    printf("No\n");
                    }
                }
    }
    return 0;

}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。