P5731 【深基5.习6】蛇形方阵——题解

解题思路

维护当前尚未填写区域的上、下、左、右边界。每轮依次填写上边、右边、下边和左边，然后收缩对应边界。最后使用 setw(3) 控制输出场宽。

复杂度分析

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int a[15][15];
int main(){
    int n;cin>>n;
    int top=1,bottom=n,left=1,right=n,x=1;
    while(top<=bottom&&left<=right){
        for(int j=left;j<=right;j++) a[top][j]=x++;
        top++;
        for(int i=top;i<=bottom;i++) a[i][right]=x++;
        right--;
        if(top<=bottom){for(int j=right;j>=left;j--) a[bottom][j]=x++;bottom--;}
        if(left<=right){for(int i=bottom;i>=top;i--) a[i][left]=x++;left++;}
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout<<setw(3)<<a[i][j];
        cout<<'\n';
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int a[15][15]; int main(){ int n;cin>>n; int top=1,bottom=n,left=1,right=n,x=1; while(top<=bottom&&left<=right){ for(int j=left;j<=right;j++) a[top][j]=x++; top++; for(int i=top;i<=bottom;i++) a[i][right]=x++; right--; if(top<=bottom){for(int j=right;j>=left;j--) a[bottom][j]=x++;bottom--;} if(left<=right){for(int i=bottom;i>=top;i--) a[i][left]=x++;left++;} } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cout<<setw(3)<<a[i][j]; cout<<'\n'; } return 0; }