[数据结构与算法]OpenJudge NOI 1.8 07:矩阵归零消减序列和

【题目链接】

OpenJudge NOI 1.8 07:矩阵归零消减序列和

【题目释义】

该题描述不清。
输出消减前第二行第二列的值，指的是实施整个过程前第二行第二列的值。
消减的次数是n-1次，消减前输出了n-1个值，最后还要再输出一下第二行第二列的值。

【题目考点】

1. 二维数组

2. 求最值

【解题思路】

先看题目释义，根据以该描述为准，按照题目要求一步一步做即可。

【题解代码】

解法1：

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 1e9 //表示无穷大 
int main()
{
    int n, m, a[N][N] = {}, mi;//mi：一行或一列的最小值 
    cin >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> a[i][j];
    m = n;
    for(int i = 1; i <= n; ++i)//n-1次消减，第n次循环只要输出 
    {
        cout << a[2][2] << endl;
        for(int i = 1; i <= m; ++i)//行归零 
        {
            mi = INF;
            for(int j = 1; j <= m; ++j)
            {
                if(a[i][j] < mi)
                    mi = a[i][j];
            }
            for(int j = 1; j <= m; ++j)
                a[i][j] -= mi;
        }
        for(int j = 1; j <= m; ++j)//列归零 
        {
            mi = INF;
            for(int i = 1; i <= m; ++i)
            {
                if(a[i][j] < mi)
                    mi = a[i][j];
            }
            for(int i = 1; i <= m; ++i)
                a[i][j] -= mi;
        }
        m--;//行列数减少1 
        for(int i = 1; i <= m; ++i)//删去第二行第二列
            for(int j = 1; j <= m; ++j)
            {
                if(i == 1 && j == 1)
                    continue; 
                else if(i == 1)//第一行左移 
                    a[i][j] = a[i][j+1];
                else if(j == 1)//第一列上移 
                    a[i][j] = a[i+1][j];
                else//其它的向左上方移动 
                    a[i][j] = a[i+1][j+1];
            }
    }
    return 0;
}

解法2：

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 1e9 //表示无穷大 
int main()
{
    int n, m, a[N][N] = {}, mi;//mi：一行或一列的最小值 
    cin >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> a[i][j];
    m = n;
    for(int i = 1; i <= n; ++i)//n-1次消减，第n次循环只要输出 
    {
        cout << a[2][2] << endl;
        for(int i = 1; i <= m; ++i)//行归零 
        {
            mi = INF;
            for(int j = 1; j <= m; ++j)
                mi = min(mi, a[i][j]);
            for(int j = 1; j <= m; ++j)
                a[i][j] -= mi;
        }
        for(int j = 1; j <= m; ++j)//列归零 
        {
            mi = INF;
            for(int i = 1; i <= m; ++i)
                mi = min(mi, a[i][j]);
            for(int i = 1; i <= m; ++i)
                a[i][j] -= mi;
        }
        for(int i = 2; i <= m-1; ++i)//删去第二行
            for(int j = 1; j <= m; ++j)
                a[i][j] = a[i+1][j];
        for(int j = 2; j <= m-1; ++j)//删去第二列 
            for(int i = 1; i <= m-1; ++i)
                a[i][j] = a[i][j+1];
        m--;//行列数减少1 
    }
    return 0;
}