b351 - 幻方(魔方陣)之一：奇N 階
題目描述
題目要求生成一個奇數階的幻方（魔方陣），並輸出指定位置的數字。幻方是一個正方形的數字陣列，其行、列和對角線上的數字和都相等。題目給定生成幻方的規則，從中心開始填入數字，並按照特定的規則移動到下一個位置。
解題思路
本題的核心是模擬幻方生成過程。根據題目描述，我們從中心位置開始填入數字 1，然後按照右上方的規則移動到下一個位置。如果移動後的位置超出邊界或已經填有數字，則按照題目規定的方式調整位置。這個過程重複進行，直到填滿所有數字。
程式碼中，s[i][j] 是一個二維陣列，用於儲存幻方的數字。x 和 y 分別表示當前位置的行和列。no 表示當前要填入的數字。程式碼首先初始化陣列，然後從中心位置開始填入數字，並按照題目規定的規則移動位置，直到找到合適的位置。最後，程式碼輸出指定位置的數字。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
using namespace std;
int q,xt,yt,n;
bool s[5005][5005];
int main(){
cin >> q;
while(q--){
cin >> n >> xt >> yt;
int x=1,y=n/2+1,no=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
s[i][j]=0;
s[x][y]=1;
while(x!=xt||y!=yt){
if(x-1>0&&y-1>0){
if(!s[x-1][y-1]){
--x;
--y;
}
else{
++x;
}
}
else if(x-1==0&&y-1>0){
if(!s[n][y-1]){
x=n;
--y;
}
else{
++x;
}
}
else if(x-1>0&&y-1==0){
if(!s[x-1][n]){
--x;
y=n;
}
else{
++x;
}
}
else{
++x;
}
s[x][y]=1;
++no;
}
cout << no << "\n";
}
}