思路

很有趣的一道题目~虽然是个绿题但想起来并不难

如果蛋糕只有一行,那么就很简单了。

于是考虑先按行分,再按列分

先把方格按行分为许多组,使得每组中只有一行是有草莓的,其余组都是空的,这样就可以把每组都当成只有一行草莓去做就行了。

如图:

代码

这里是官方题解的代码,稍加改动并加上了注释方便理解,注释仅供参考

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int H, W, K, A[309][309], num=0;
int cnt[309];
char c[309][309];
void solve(int cl, int cr) {
    vector<int> P;
    for (int i = cl; i <= cr; i++) {//此处在每排找是有时最后一行或第一行也是空行,必须全部搜一遍
        for (int j = 1; j <= W; j++) {
            if (c[i][j] == '#') P.push_back(j);
        }
    }
    for (int i = 0; i < P.size(); i++) {
        int v1 = 1, v2 = W;
        if (i >= 1) v1 = P[i - 1] + 1;//特判开头为空
        if (i < (int)P.size() - 1) v2 = P[i];//特判末尾为空
        num++;//下一组
        for (int j = cl; j <= cr; j++) {
            for (int k = v1; k <= v2; k++) A[j][k] = num;
        }
    }
}
int main() {
    cin >> H >> W >> K;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> c[i][j];
            if (c[i][j] == '#') cnt[i]++;//记录每行的草莓数
        }
    }
    vector<int> vec;
    for (int i = 1; i <= H; i++) { 
        if (cnt[i] >= 1)
            vec.push_back(i); //将草莓数不为0的一行放进vector
    }
    for (int i = 0; i < vec.size(); i++) {
        int v1 = 1, v2 = H;
        if (i >= 1) v1 = vec[i - 1] + 1;//特判开头几行为空
        if (i < (int)vec.size() - 1) v2 = vec[i];//特判末尾几行为空
        solve(v1, v2);
    }
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (j >= 2) cout << " "; cout << A[i][j];
        }
        cout << endl;
    }
    return 0;
}

原题链接:link洛谷 | linkat