压缩技术

洛谷·深入浅出 · 代码 · cpp · 难度 3/5 · 共 684 字

按压缩码还原 N×N 的 01 点阵

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1411
// 题意（压缩）：输入 N×N 的 0/1 点阵图，按 行优先 生成压缩码——先输出 N，再按 0/1 交替输出连续段长度。
// 思路：读入点阵拼成一行，从头起交替统计连续 0、连续 1 的个数，依次输出 N 与这些段长。
// 复杂度：O(N^2)。
// 易错点：首段一定是 0（点阵从左上角起）；段长之间用空格隔开；先输出 N 再输出段长。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
    vector<string> rows;
    string line;
    while(cin >> line) rows.push_back(line);
    int N = rows[0].size();
    string flat;
    for(auto &r : rows) flat += r;
    cout << N;
    char cur = flat[0];
    int cnt = 0;
    for(char c : flat){
        if(c == cur) cnt++;
        else { cout << " " << cnt; cur = c; cnt = 1; }
    }
    cout << " " << cnt << endl;
    return 0;
}

压缩技术

正文

洛谷·深入浅出的其它内容