牛客小白月赛2 A数字方阵【随机】【找规律】

链接：https://www.nowcoder.com/acm/contest/86/A

题目描述

 总是对数字的神秘感感到好奇。这次，他在纸上写下了  个从 到 的数字，并把这些数字排成了 的方阵。他惊奇地发现，这个方阵中每行、每列和两条主对角线上的数字之和都不一样。他想要更多的方阵，但他再写不出来了。于是他㕛跑来找你，请你给他一个边长为  的满足上述性质的方阵。

输入描述:

输入共一行，一个整数 

 ，意义同题面描述。

输出描述:

输出共 

 行，每行 

 个整数，表示答案方阵。
输出任意一种可行方案即可。

输入例子:

3

输出例子:

1 2 3

8 9 4

7 6 5

-->

示例1

输入

3

输出

1 2 3

8 9 4

7 6 5

备注:

 

思路:

1.  1~(n-1) 列，按行 依次填入数字。 n 列从第一行到第n行依次填入数字

2. 另类方法，随机法 ,原帖 https://blog.csdn.net/jeatiaime813/article/details/80034407

 

AC码：

 #include <iostream>

 using namespace std;

 int main(){

     int n;

     cin>>n;

     int cnt=,fine = n*n-n+;

     for(int i=;i<n;i++)

         for(int j=;j<n;j++)

             if(j==n-)

                 cout<<fine++<<endl;

              else

                 cout<<cnt++<<" ";

     return ;

 }

 

随机大法：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<ctime>

 #include<set>

 using namespace std;

 int a[][];

 int n;

 void aaa()

 {

     for (int i = ; i <= n; i++)

     {

         for (int j = ; j <= n; j++)

         {

             if (j == n) printf("%d\n", a[i][j]);

             else printf("%d ", a[i][j]);

         }

     }

 }

 void hhh()

 {

     for (int i = ; i <= n; i++)

         for (int j = ; j <= n; j++)

             a[i][j] = (i - ) * n + j;

     for (int i = ; i <= n; i++)

     {

         for (int j = ; j <= n; j++)

         {

             int rx = rand() % n + ;

             int ry = rand() % n + ;

             swap(a[i][j], a[rx][ry]);

         }

     }

 }

 bool judge()

 {

     int r[], c[];

     int z1 = , z2 = ;

     memset(r, , sizeof(r));

     memset(c, , sizeof(c));

     for (int i = ; i <= n; i++)

     {

         for (int j = ; j <= n; j++)

         {

             r[i] += a[i][j];

             c[j] += a[i][j];

             if (i == j) z1 += a[i][j];

             if (i + j == n + ) z2 += a[i][j];

         }

     }

     set<int> st;

     for (int i = ; i <= n; i++)

     {

         st.insert(r[i]);

         st.insert(c[i]);

     }

     st.insert(z1);

     st.insert(z2);

     if ((int)st.size() == ( * n + )) return true;

     else return false;

 }

 int main()

 {

     srand((unsigned)time(NULL));

     while (scanf("%d", &n) != EOF)

     {

         if (n == )

         {

             printf("1 2 3\n8 9 4\n7 6 5\n");

         }

         else {

             int maxtime = ;

             while (maxtime--)

             {

                 hhh();

                 if (judge()) break;

             }

             aaa();

         }

     }

     return ;

 }