矩阵归零消减序列和(openjudge 1.8.07)

aaant

飞天热干面教信徒

题目描述

给定一个 n \times n 的矩阵（ 3 \le n \le 100 ，元素的值都是非负整数）。通过 n-1 次实施下述转换过程，可把这个矩阵最终转换成一个 1 \times 1 的矩阵。每次的过程如下：

首先对矩阵进行行归零：即对每一行上的所有元素，都在其原来值的基础上减去该行上的最小值，保证相减后的值仍然是非负整数，且这一行上至少有一个元素的值为 0 。
接着对矩阵进行列归零：即对每一列上的所有元素，都在其原来值的基础上减去该列上的最小值，保证相减后的值仍然是非负整数，且这一列上至少有一个元素的值为 0 。
然后对矩阵进行消减：即把 n \times n 矩阵的第二行和第二列删除，使之转换为一个 (n-1) \times (n-1) 的矩阵。
下一次过程，对生成的 (n-1) \times (n-1) 矩阵实施上述过程。显然，经过 n-1 次上述过程， n \times n 的矩阵会被转换为一个 1 \times 1 的矩阵。

请求出每次转换前位于第二行第二列的元素的值。

输入格式

第一行是一个整数 n 。

接下来 n 行，每行有 n 个正整数，描述了整个矩阵。相邻两个整数间用单个空格分隔。

输出格式

输出为 n 行，每行上的整数为对应矩阵转换过程中，每次转换前位于第二行第二列的元素的值。

样例 #1

样例输入 #1

样例输出 #1

3
0

题解

思路

本题有一个明显的错误，题目要求每次消减前输出第二行第二列的数值，总共只能进行 n - 1 次消减，所以输出应该只有 n - 1 个，而题目要求输出 n 个数值是不合理的，所以一般的做法拿不到满分。
洛谷里的 T143450 是同样的题目，输出要求修改过了，可以正常提交。
但奇怪的是在 openjudge 中还是有人能 AC，下面分析下能 AC 的原因。

常规代码

本题比较简单，直接用代码模拟即可，python 可以很方便地对列表进行删除的操作，先给出 python 代码

n = int(input())
mat = [[int(x) for x in input().split()] for _ in range(n)]
def rm(n):
    for i in range(n):
        m = min(mat[i])
        for j in range(n):
            mat[i][j] -= m
def cm(n):
    for j in range(n):
        m = mat[0][j]
        for k in range(1, n):
            if mat[k][j] < m:
                m = mat[k][j]
        for i in range(n):
            mat[i][j] -= m
x = n
for i in range(n - 1):
    print(mat[1][1])
    rm(x)
    cm(x)
    # ans = mat[1][1]
    # 删除第二行
    mat.pop(1)
    x -= 1
    # 删除第二列
    for j in range(x):
        mat[j].pop(1)
# print(ans)

C++ 中使用 vector 也可以做类似 python 的操作，如果使用数组就不可行了，这里有两种思路。
思路一：
每次都是删除第二行和第二列，从整个矩阵来看，实际上第一次删除的是第二行和第二列，第二次删除的是第三行和第三列，第 n - 1 次删除的是第 n 行和第 n 列。因此用一个变量 s 来记录每次要删除的行，删完之后 s++ ，所谓的删除就是把第 s 行和第 s 列的数值都设为无穷大，每次要输出的值都是第 s 行和 s 列的值，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
const int inf = 0x7fffffff;
int n, s = 2;
int mat[N][N];
void rm() {
    for (int i = 1; i <= n; i++) {
        int t = mat[i][1];
        for (int j = s; j <= n; j++) t = min(t, mat[i][j]);
        mat[i][1] -= t;
        for (int j = s; j <= n; j++) {
            mat[i][j] -= t;
void cm() {
    for (int j = 1; j <= n; j++) {
        int t = mat[1][j];
        for (int i = s; i <= n; i++) t = min(t, mat[i][j]);
        mat[1][j] -= t;
        for (int i = s; i <= n; i++) {
            mat[i][j] -= t;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mat[i][j];
    // int ans;
    for (int i = 0; i < n - 1; i++) {
        cout << mat[s][s] << endl;
        rm();
        cm();
        // ans = mat[s][s];
        for (int i = 1; i <= n; i++) {
            mat[i][s] = inf;
            mat[s][i] = inf;