b580 - 一條蛇
題目描述
題目要求模擬一條螺旋狀的蛇，蛇的寬度由輸入決定。輸出蛇的數字排列，數字按照螺旋順序遞增。
解題思路
這題的核心在於模擬螺旋填數的過程。程式首先預先計算好蛇的數字排列，儲存在一個二維陣列 ans 中。然後，根據輸入的蛇的寬度，從陣列中提取出對應大小的子矩陣並輸出。螺旋填數的邏輯是：先向右，再向下，再向左，再向上，重複這個過程直到填滿整個矩陣。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是蛇的寬度。預先計算陣列需要 O(n^2) 的時間，輸出子矩陣也需要 O(n^2) 的時間。
- 空間複雜度: O(n^2)，用於儲存蛇的數字排列的二維陣列
ans。
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
int ans[105][105];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a(1),w(0),i(51),j(51),n,k(51),na;
ans[i][j]=1;
while(k--){
n=++w;
while(n--)
ans[i][++j]=++a;
n=w;
while(n--)
ans[--i][j]=++a;
n=++w;
while(n--)
ans[i][--j]=++a;
n=w;
while(n--)
ans[++i][j]=++a;
}
cin >> n;
while(cin >> n){
n>>=1;
na=51+n;
n=51-n;
for(int x(n);x<=na;++x){
for(int y(n);y<=na;++y)
cout << setw(5) << ans[x][y] ;
cout << "\n";
}
cout << "\n";
}
}