二维数组右上左下遍历

GitHub跳转原题关系图返回列表

按对角线编号确定顶端或右端起点，再沿左下方向输出全部元素。

OJ: noi_openjudge

题目 ID: ch0108-21

难度:入门

标签:矩阵模拟遍历python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. Python代码
  7. C++代码
    1. 复杂度
    2. 总结

题意

从左上向右下逐条对角线遍历矩阵，每条对角线沿左下方向输出。

思路

第 dd 条对角线的起点在首行或最右列。确定起点后反复执行“行加一、列减一”，直到出界。

代码

cpp
#include <cstdio>
#include <cstring>


int n,m;
int a[1400][1400];

void init(){
    scanf("%d%d",&n,&m);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
}
void print(int x,int y){
    while( x >= 1 && x <= n && y >=1 && y <=m){
        printf("%d\n",a[x][y]);
        x +=1;
        y -=1;
    }
}
int main(){
    init();
    int i;
    for (i=1;i<=n+m-1;i++){
        int x,y;
        if( i <= m){
            y = i;
            x = 1;
        }
        else {
            y = m;
            x = (i-m) +1;
        }
        print(x,y);
        //printf("%d %d\n",x,y);
    }
    return 0;
}

复杂度

总结

Python代码

python
row_count, column_count = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(row_count)]

for diagonal in range(row_count + column_count - 1):
    row = 0 if diagonal < column_count else diagonal - column_count + 1
    column = diagonal if diagonal < column_count else column_count - 1
    while row < row_count and column >= 0:
        print(matrix[row][column])
        row += 1
        column -= 1

C++代码

cpp
#include <cstdio>
#include <cstring>


int n,m;
int a[1400][1400];

void init(){
    scanf("%d%d",&n,&m);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
}
void print(int x,int y){
    while( x >= 1 && x <= n && y >=1 && y <=m){
        printf("%d\n",a[x][y]);
        x +=1;
        y -=1;
    }
}
int main(){
    init();
    int i;
    for (i=1;i<=n+m-1;i++){
        int x,y;
        if( i <= m){
            y = i;
            x = 1;
        }
        else {
            y = m;
            x = (i-m) +1;
        }
        print(x,y);
        //printf("%d %d\n",x,y);
    }
    return 0;
}

复杂度

每个元素输出一次，时间复杂度为 O(rc)O(rc)，矩阵空间为 O(rc)O(rc)。

总结

对角线遍历可用“对角线编号 + 固定步长”统一实现。