AcWing 753. 平方矩阵 I

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 753. 平方矩阵 I 原题链接困难

作者：

小张同学 , 2020-03-05 17:09:37 , 所有人可见 , 阅读 12201

231

232

我本来的想法是：每次都用新的数组去覆盖，但我写不出来。。等下次再看这道题时看看能不能写出来
然后看了一些大佬的想法，写个小总结

方法一：来自y总的想法并加了小修改~

y总的做法是： 对于奇数每一圈距离中心点的距离相等; 中心点 - 横纵坐标中的最大值
对于偶数： a[i][j] = n / 2 - max(min(abs(i - n / 2), abs(i - (n - 1) / 2)), min(abs(j - n / 2), abs(j - (n - 1) / 2)));
这个好像比奇数多了一个判断min(abs(i - n / 2), abs(i - (n - 1) / 2)) ,其实我没懂。。应该是种技巧吧hhh
更正：规律是每个数等于它到上下左右四条边的距离的最小值。(from yls的解答)
我在偶数上改了一下，偶数没有中心点，那我就自己虚拟一个中心点，这个中心点就得是小数了，不影响距离~还得加上1

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>


using namespace std;

const int N = 110;

int n;
int a[N][N];

int main()
{
    while(cin >> n, n)
    {
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
            {
                if (n % 2)
                    a[i][j] = (n + 1) / 2 - max(abs(i - n / 2), abs(j - n / 2));
                else 
                    a[i][j] = (n - 1) / 2.0 - max(abs((n - 1) / 2.0 - i), abs((n - 1) / 2.0 - j)) + 1;
            }

        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < n; j ++ ) 
                cout << a[i][j] << ' ';
            cout << endl;
        }

        cout << endl;
    }



    return 0;
}

方法二：不用数组，找数和坐标的关系

while(cin >> n, n)
{
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
            cout << min(min(i, j), min(n - i + 1, n - j + 1)) << ' ';
        cout << endl;
    }   
    cout << endl;

}

方法三：对称着来写(这个坐标我看了好久才想明白, 我真是笨死了)

平方矩阵I.png

while(cin >> n, n)
{
    for (int i = 0; i < n; i ++ )
    {
        for (int j = i; j < n - i; j ++ )
        {
            a[j][i] = a[i][j] = i + 1;
            a[j][n - i - 1] = a[n - i - 1][j] = i + 1;
        }
    }
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
            cout << a[i][j] << ' ';
        cout << endl;
    }
    cout << endl;

}

47 评论

低能所以不学算法 2022-11-24 00:28

萌新这样写ac了

#include<iostream>
using namespace std;

int arr[100][100] = { 0 };
int main()
{
    int n;
    int t;
    while (cin>>n) {
        if(n==0) return 0;
        int m = 0;
        t = n;

        for (n; n != 0;n--) {


            for(int i = m; i < n; i++) {
                arr[m][i] = m+1;
                arr[i][m] = m+1;
                arr[i][n-1] = m+1;
                arr[n - 1][i] = m+1;

            }

            m++;

        }

       for (int i = 0; i < t; i++) {
           for (int j = 0; j < t; j++) {
            cout << arr[i][j] << ' ';

           }
        cout << endl;

       }

       cout << endl;

    }
}

Xin-acwing 2023-02-10 11:07

我一开始也是想着在数组里面直接填不就完了，但是想不出来怎么填，感谢大佬

低能所以不学算法 2023-02-17 20:35 回复了 Xin-acwing 的评论

一起加油呀

Gentle_信仰 8个月前回复了低能所以不学算法的评论

太厉害了大佬我知道怎么做但是写不出来很尴尬、

才浅_5 2022-07-13 15:48

牛逼啊！同学，为你非常认真的学习态度点赞。👍

叶超 2023-05-04 15:46

#include<iostream>
#include<math.h>

using namespace std;

int main(){
    int n;
    double center;
    while(cin>>n, n){
        center = (n-1)/2.0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << center - max(abs(center - i), abs(center - j)) + 1<< " ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

设置中心点，然后找每圈距离中心点隔了几圈，然后计算得到值

给算法画个句号 2023-12-07 17:56

很妙

暴躁小蟑螂 2022-11-08 09:47

兄弟太牛了，跟你点个赞

管静雯 2022-10-09 21:17

我看不懂，脑子比较钝

管静雯 2022-10-09 21:17

家人们，谁能跟我讲讲第二种方法吗

楚时月 2022-11-03 01:29

可以把最外侧一圈看作一堵墙，某一点的值就是它到墙的距离，最中间距离墙最远，值最大。

阿尔托莉雅_1 2023-10-01 23:52 回复了楚时月的评论

赞赞赞，懂了

是奥契丝呀 2023-10-28 20:24

不太要脑子的做法
#include[HTML_REMOVED]
using namespace std;

int main()
{
int i,j,k,n;

while(cin>>n&&n!=0)
{
    int arr[n][n];

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

    for(k=0;k<(n+1)/2;k++)
    {
        for(i=k;i<n-k;i++)
        {
            for(j=k;j<n-k;j++)
            arr[i][j]+=1;
        }
    }

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%d ",arr[i][j]);
        }

        printf("\n");
    }

    printf("\n");
}

return 0;

}

Allegramente. 2023-09-23 22:24

对于第三种做法的说明：
关于整圈的下标，[i][j], [j][i], [n-i-1][j], [j][n-i-1]四个下标可以完成整圈的遍历，外层循环写为i从0到n-1，j写为从i到n-i-1。
构造思路大概是在四条边以特定方向遍历整条边，所以有四个点，每个点的位置是一维变化的。这个关系来源是确定好[i][j]后取主对角线对称得到[j][i]，又观察到[i][j]和[n-i-1][j]的关系（横坐标对称），再取主对角线对称得到所有点。
理论上还可以构造四个同为逆时针方向变化的坐标，但上述构造方法浅显易懂。

图灵酱 2023-05-23 17:21

啊，ε=(´ο｀*)))唉哎，萌新还是看不懂

图灵酱 2023-05-23 17:22

min(min是啥意思啊

童蒙 2023-09-14 12:01 回复了图灵酱的评论

看完整，i和j取最小值，n - i + 1和n - j + 1取最小值，然后再把这两个最小值取最小值，就是直接根据坐标推出来的

高叶 2023-02-10 14:37

感觉第三种做法真的很nice

V0yager 2个月前

用覆盖来做

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin >> n,n > 0)
    {
        int a[n][n] = {0};
        for(int i = 0;i < n / 2 + 1;i ++) // n/2向上取整层覆盖
        {
            for(int j = i;j < n - i;j ++)
            {
                for(int k = i;k < n - i;k ++)
                    a[j][k] = i + 1;
            }
        }//覆盖完成

        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}

汪超 9个月前

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i ++)
        {
            for (int j = 0; j < n; j ++)
                cout << min(min(n - i - 1,i), min(n - j - 1,j)) + 1 << " ";
            cout << endl;
        }
        cout << endl;  
    }

    return 0;
}

接舆小楚 11个月前

#include<iostream>
using namespace std;
int main()
{
    int n,i,j;
    cin>>n;

    while(n){
        if(n==1)
        {
            cout<<n<<endl<<endl;
            cin>>n;
        }
        else
        {
            int a[101][101]={0};
            for(int num=1;num<n;num++){
                for(j=0;j<n;j++){
                    if(!a[num-1][j])
                    a[num-1][j]=num;//a[0][0~2]
                }
                for(j=0;j<n;j++){
                    if(!a[n-num][j])
                    a[n-num][j]=num;//a[2][0~2]
                }
                for(i=0;i<n;i++){
                    if(!a[i][num-1])
                    a[i][num-1]=num;
                }
                for(i=0;i<n;i++){
                    if(!a[i][n-num])
                    a[i][n-num]=num;
                }
            }
            for(i=0;i<n;i++){
                for(j=0;j<n;j++){
                cout<<a[i][j]<<" ";
                }
            cout<<endl;
            }
        cout<<endl;

        cin>>n;

        }
    }

    return 0;
}
//他奶奶的，花了我1小时终于搞出来了

接舆小楚 11个月前

太暴力了

未定 2023-11-21 22:14

那个while(cin >> n, n)里面的，n)怎么理解呀？，求大佬告知

LiuHH 10个月前

while里面的n就是一个判断的作用，即当输入的n为0时，则表示条件为假，退出循环

Jinpei_Matsuda 2023-05-10 14:59

#include<iostream>
using namespace std;

int main(){

    int n;
    while(cin >>n, n > 0){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            {
                if(j != n - 1) cout << min(min(n - i, n - j), min(i + 1, j + 1)) << " ";
                else cout << min(min(n - i, n - j), min(i + 1, j + 1)) << endl;
            }
        cout << endl;
    }

    return 0;
}

Jinpei_Matsuda 2023-05-10 15:00

这个只需要考虑每个元素到四条边距离的最小值即可

巷口风铃 2023-05-03 18:26

//一个萌萌的由外及内的边框做法
#include<iostream>
#include<cstdio>
using namespace std;

int n;
int m[101][101];


int main(){
    while(scanf("%d",&n),n!=0){
        int k= 1;
        for(int i = k;i<=n;i++)
            m[1][i] = k;
        for(int i = k;i<=n;i++)
            m[n][i] = k;
        for(int i = k;i<=n;i++)
            m[i][1] = k;
        for(int i = k;i<=n;i++)
            m[i][n] = k;

        int t = n;
        while(1){
            k++;n--;
            if(k>n) break;

            for(int i = k;i<=n;i++)
                m[k][i] = k;
            for(int i = k;i<=n;i++)
                m[n][i] = k;
            for(int i = k;i<=n;i++)
                m[i][k] = k;
            for(int i = k;i<=n;i++)
                m[i][n] = k;

        }

        for(int i = 1;i<=t;i++)
            for(int j = 1;j<=t;j++)
                if(j!=t)
                    printf("%d ",m[i][j]);
                else
                    printf("%d\n",m[i][j]);

        printf("\n");
    }


    /*

    for(int i = 0;i<12;i++)
        for(int j = 0;j<12;j++)
        if(j!=11)
            printf("%.1f ",M[i][j]);
        else printf("%.1f\n",M[i][j]);

    */

    return 0;
}

_O.o_ 2023-05-02 13:51

orz

acwing_6539 2023-03-16 22:57

这样写AC了

#include<iostream>
using namespace std;

const int N = 105;
int a[N][N];

int main(){
    int n;
    cin >> n;
    while(n != 0){
        int up = 0 , down = n - 1 , left = 0 , right = n - 1;       //设置最外一条边的位置作为一个基准
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++){
                if(i == up || i == down || j == left || j == right)     //如果元素位置在最外一条边
                    a[i][j] = 1;
                for(int k = 0; k < n; k ++){            //否则元素位置在内部，按一定规律进行处理
                    if((i >= up + k + 1 && i <= down - k - 1) && (j > left + k && j < right - k))
                        a[i][j] = k + 2;
                }
            }
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                cout << a[i][j] << ' ';   
            }
            cout << endl;
        }
        cout << endl;
        cin >> n;
    }
    return 0;
}

20100928 2023-01-20 15:48

6666

黑黑的憨憨 2023-01-09 22:52

牛逼啊！！！兄弟

App 内打开