按副对角线编号交替方向填充，构造 1 到 n 平方的蛇形方阵。
OJ: noi_openjudge
题目 ID: ch0108-24
难度:入门
标签:矩阵模拟构造python
日期: 2026-07-30 23:01
题意
用
思路
同一副对角线的坐标满足 row + column = diagonal。每条对角线先求合法行范围；奇数编号按行递增填充，偶数编号反向填充，方向自然交替。
代码
cpp
#include <cstdio>
int m,n;
int map[200][200];
int idx=0;
//down up
int fx[] = {1,-1};
int fy[] = {-1,1};
bool in_map(int x,int y){
if( x >=1 && x <=n && y >=1 && y <= n)
return 1;
return 0;
}
void set_num(int x,int y,int dir){
while( in_map(x, y)){
map[x][y] = ++idx;
x += fx[dir];
y += fy[dir];
}
}
void get_start(int num,int &x,int &y){
if( num % 2 == 0){
if( num <= n){
x = 1;
y = num;
return;
}
y = n;
x = ( num % n)+1;
return ;
}
if( num <=n ){
y = 1;
x = num;
return;
}
x = n;
y = ( num % n)+1;
}
int main(){
scanf("%d",&n);
int i,j,k,l;
int x,y;
for (i=1;i<2*n;i++){
get_start(i, x, y);
set_num(x, y, i % 2);
}
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
printf("%d ",map[i][j]);
}
printf("\n");
}
return 0;
}复杂度
总结
Python代码
python
size = int(input())
matrix = [[0] * size for _ in range(size)]
number = 1
for diagonal in range(2 * size - 1):
row_start = max(0, diagonal - size + 1)
row_end = min(size - 1, diagonal)
rows = range(row_start, row_end + 1)
if diagonal % 2 == 0:
rows = reversed(list(rows))
for row in rows:
column = diagonal - row
matrix[row][column] = number
number += 1
for row in matrix:
print(*row)C++代码
cpp
#include <cstdio>
int m,n;
int map[200][200];
int idx=0;
//down up
int fx[] = {1,-1};
int fy[] = {-1,1};
bool in_map(int x,int y){
if( x >=1 && x <=n && y >=1 && y <= n)
return 1;
return 0;
}
void set_num(int x,int y,int dir){
while( in_map(x, y)){
map[x][y] = ++idx;
x += fx[dir];
y += fy[dir];
}
}
void get_start(int num,int &x,int &y){
if( num % 2 == 0){
if( num <= n){
x = 1;
y = num;
return;
}
y = n;
x = ( num % n)+1;
return ;
}
if( num <=n ){
y = 1;
x = num;
return;
}
x = n;
y = ( num % n)+1;
}
int main(){
scanf("%d",&n);
int i,j,k,l;
int x,y;
for (i=1;i<2*n;i++){
get_start(i, x, y);
set_num(x, y, i % 2);
}
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
printf("%d ",map[i][j]);
}
printf("\n");
}
return 0;
}复杂度
填充和输出每格一次，时间和空间复杂度均为
总结
蛇形对角线填充可归结为“固定坐标和的斜线”与方向交替。