图像压缩算法：删除重复行和列

图像压缩算法：删除重复行和列

有一个H行W列像素组成的图像, 从上往下数第i行, 从左往右数第j列的像素用ai,j来表示. 图像只由黑白两种颜色组成, ai,j=0表示黑色, ai,j=1表示白色.现在想要压缩这个图像, 打算按照如下方法压缩: 如果存在相邻的两行完全一样, 就删除其中一行.如果存在相邻的两列完全一样, 就删除其中一列.重复以上操作直到无法再进行删除为止, 可以证明最终结果和删除顺序无关.

输入

第一行, 2个整数 H, W. 接下来H行, 每行W个整数. 表示图像. 0表示黑色,1表示白色, 数与数之间用空格分隔。

输出

输出压缩后的图像, 数与数之间用空格分隔.

样例输入

3 3
1 1 0
1 1 0
0 0 1

样例输出

1 0
0 1

提示

数据范围：1≤H,W≤50

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> image(H, vector<int>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> image[i][j];
        }
    }
    
    vector<bool> row_deleted(H, false);
    vector<bool> col_deleted(W, false);
    
    // 删除相邻的相同行
    for (int i = 1; i < H; i++) {
        if (!row_deleted[i] && image[i] == image[i-1]) {
            row_deleted[i] = true;
        }
    }
    
    // 删除相邻的相同列
    for (int j = 1; j < W; j++) {
        bool col_same = true;
        for (int i = 0; i < H; i++) {
            if (image[i][j] != image[i][j-1]) {
                col_same = false;
                break;
            }
        }
        if (col_same) {
            col_deleted[j] = true;
        }
    }
    
    // 输出压缩后的图像
    for (int i = 0; i < H; i++) {
        if (!row_deleted[i]) {
            for (int j = 0; j < W; j++) {
                if (!col_deleted[j]) {
                    cout << image[i][j] << " ";
                }
            }
            cout << endl;
        }
    }
    
    return 0;
}