题解：B4199 [常州市赛 2020] 旋转数塔

wenqinghua1001 · 2025-06-22 09:48:51 · 题解

思路

不难发现，从外面数，奇数圈是顺时针填数，偶数圈是逆时针填数，只需一层一层暴力即可。

设 a_{i,j} 表示这个矩阵第 i 行，第 j 列的答案。如果 n 是奇数，那么 a_{(n+1) \div 2,(n+1) \div 2}=n^2。

顺时针

如果顺时针，那么把这一圈分为四份。上面这幅图最外面的一层，分为四份就是：

第一份：1,2,3,4。\ 第二份：5,6,7,8。\ 第三份：9,10,11,12。\ 第四份：13,14,15,16。

可以找到其中的规律，第一份列数增加，第二份行数增加，第三份列数减少，第四份行数减少。

void dfs1(int r){
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y--;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x--;
    }
    x++,y++;// 为下一层做准备。
}

逆时针

如果逆时针，那么也把这一圈分为四份。这幅图从外面数的第二层，分为四份就是：

第一份：17,18。\ 第二份：19,20。\ 第三份：21,22。\ 第四份：23,24。

可以找到其中的规律，第一份行数增加，第二份列数增加，第三份行数减少，第四份列数减少。

int dfs2(int r){
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x--;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y--;
    }
    x++,y++;// 为下一层做准备。
}

代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
int a[101][101],sum=0,x=1,y=1;
void dfs1(int r){
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y--;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x--;
    }
    x++,y++;// 为下一层做准备。
}
int dfs2(int r){
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y++;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        x--;
    }
    for(int i=1;i<=r;i++){
        a[x][y]=++sum;
        y--;
    }
    x++,y++;// 为下一层做准备。
}
int main(){
    int n;
    cin>>n;
    if(n%2==1) a[n/2+1][n/2+1]=n*n;
    for(int i=n-1,j=1;i>=1;i-=2,j++){
        if(j%2==1){
            // 顺时针
            dfs1(i); 
        }
        else{
            // 逆时针
            dfs2(i); 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}