矩阵归零消减序列和

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

每轮先记录第二行第二列，再行列归零并删除第二行第二列。

OJ: noi_openjudge

题目 ID: ch0108-07

难度:普及/提高-

标签:矩阵模拟python

日期: 2026-07-30 23:01

目录

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

题意

反复对方阵行归零、列归零并删除第二行第二列，输出每次消减前该位置的值，最后输出 1×11\times1 阶段的 0。

思路

当前矩阵大小大于 11 时，先记录 matrix[1][1]。之后每行减行最小值、每列减列最小值，再通过切片删除下标为 11 的行和列。行列归零不会改变非负性。

代码

cpp
/* 题目的意思有歧义
 * 可以得到n个矩阵，分别对n个矩阵的map[2][2]输出
 *
 * */
#include <cstdio>

#define inf 0x7f7f7f7f

int n;
int map[200][200];
void hang(int l){
    int i,j;
    for (i=1;i<=l;i++){
        int min = inf;
        for (j=1;j<=l;j++){
            if( min > map[i][j])
                min = map[i][j];
        }
        for (j=1;j<=l;j++){
            map[i][j] -=min;
        }
    }
}

void lie(int l){
    int i,j;
    for (i=1;i<=l;i++){
        int min = inf;
        for (j=1;j<=l;j++){
            if( min > map[j][i])
                min = map[j][i];
        }
        for (j=1;j<=l;j++){
            map[j][i] -=min;
        }
    }
}

void xiao(int l){
    int i,j;
    for (i=1;i<=l;i++){
        for (j=2;j<l;j++){
            map[i][j] = map[i][j+1];
        }
    }
    for (i=1;i<l;i++){
        for (j=2;j<l;j++){
            map[j][i] = map[j+1][i];
        }
    }
}

void print(int l){
    int i,j;
    for (i=1;i<=l;i++){
        for (j=1;j<=l;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    printf("========\n");
}

int main(){
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            scanf("%d",&map[i][j]);
        }
    }
    for (i=n;i>=1;i--){
        if( i == 0)
            printf("0");
        else
        printf("%d\n",map[2][2]);
        hang(i);
        lie(i);
        xiao(i);
        //print(i-1);
    }

    return 0;
}

复杂度

总结

Python代码

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

while len(matrix) > 1:
    print(matrix[1][1])

    for row in matrix:
        minimum = min(row)
        for column in range(len(row)):
            row[column] -= minimum

    for column in range(len(matrix)):
        minimum = min(row[column] for row in matrix)
        for row in matrix:
            row[column] -= minimum

    matrix = [row[:1] + row[2:] for row in matrix[:1] + matrix[2:]]

print(0)

C++代码

cpp
/* 题目的意思有歧义
 * 可以得到n个矩阵，分别对n个矩阵的map[2][2]输出
 *
 * */
#include <cstdio>

#define inf 0x7f7f7f7f

int n;
int map[200][200];
void hang(int l){
    int i,j;
    for (i=1;i<=l;i++){
        int min = inf;
        for (j=1;j<=l;j++){
            if( min > map[i][j])
                min = map[i][j];
        }
        for (j=1;j<=l;j++){
            map[i][j] -=min;
        }
    }
}

void lie(int l){
    int i,j;
    for (i=1;i<=l;i++){
        int min = inf;
        for (j=1;j<=l;j++){
            if( min > map[j][i])
                min = map[j][i];
        }
        for (j=1;j<=l;j++){
            map[j][i] -=min;
        }
    }
}

void xiao(int l){
    int i,j;
    for (i=1;i<=l;i++){
        for (j=2;j<l;j++){
            map[i][j] = map[i][j+1];
        }
    }
    for (i=1;i<l;i++){
        for (j=2;j<l;j++){
            map[j][i] = map[j+1][i];
        }
    }
}

void print(int l){
    int i,j;
    for (i=1;i<=l;i++){
        for (j=1;j<=l;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    printf("========\n");
}

int main(){
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            scanf("%d",&map[i][j]);
        }
    }
    for (i=n;i>=1;i--){
        if( i == 0)
            printf("0");
        else
        printf("%d\n",map[2][2]);
        hang(i);
        lie(i);
        xiao(i);
        //print(i-1);
    }

    return 0;
}

复杂度

各阶段总工作量为 O(n3)O(n^3)，矩阵空间复杂度为 O(n2)O(n^2)。

总结

多阶段矩阵模拟必须严格区分“记录值”“归零”和“删除”的执行顺序。