3035. 次大黑区域

Deuchie

考点:连通块,次大。

int main() {
    using namespace std;
    uint32_t t; cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        uint32_t n, m; cin >> n >> m;
        constexpr size_t MAXNM = 102;
        array<array<char, MAXNM>, MAXNM> image;
        for (uint32_t i = 1; i <= n; ++i) {
            for (uint32_t j = 1; j <= m; ++j) {
                cin >> image[i][j];
            }
        }
        vector<uint32_t> black_tiles;
        for (uint32_t i = 1; i <= n; ++i) {
            for (uint32_t j = 1; j <= m; ++j) {
                if (image[i][j] == '1') {
                    uint32_t cnt = 1;
                    image[i][j] = '\0';
                    struct Pos {
                        uint32_t x, y;
                    };
                    vector<Pos> stack{{i, j}};
                    do {
                        auto pos = stack.back();
                        stack.pop_back();
                        constexpr int32_t dx[4]{-1, 1, 0, 0};
                        constexpr int32_t dy[4]{0, 0, -1, 1};
                        for (uint32_t i = 0; i < 4; ++i) {
                            auto nx = pos.x + dx[i];
                            auto ny = pos.y + dy[i];
                            if (image[nx][ny] == '1') {
                                ++cnt;
                                image[nx][ny] = '\0';
                                stack.push_back({nx, ny});
                            }
                        }
                    } while (!stack.empty());
                    black_tiles.push_back(cnt);
                }
            }
        }
        sort(black_tiles.begin(), black_tiles.end(), greater<>());
        auto ed = unique(black_tiles.begin(), black_tiles.end());
        if (ed - black_tiles.begin() <= 1) {
            puts("0");
        } else {
            printf("%u\n", black_tiles[1]);
        }
    }
}
Master X

dfs入门题加强版。
……自己练吧……

10175101109

直接用递归的话在最大的样例那里似乎出现了栈溢出,建议用循环写DFS部分

你当前正在回复 博客/题目
存在问题!