题解归档 - cf104118J

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118J
• 本地来源：problems/cf104118J/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/J
• 原始标题：Gym 104118J - Junior Steiner Three

思路

Gym 104118J - Junior Steiner Three

There are exactly three land cells. In a grid with 4-neighbor movement, the minimum rectilinear Steiner tree for three terminals is obtained by connecting all three to a coordinate-wise median point.

Let (cx, cy) be the median of the three row coordinates and the median of the three column coordinates. Paint any Manhattan path from each original land cell to (cx, cy). The union is connected, keeps all original land cells, and has minimum possible number of added cells.

Complexity: O(r c).

Checks:

• sample 1 shape differs from sample output but has the same optimal size/connectivity

代码

来源：problems/cf104118J/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c;
    cin >> r >> c;
    vector<string> g(r);
    for (auto &s : g) cin >> s;

    vector<pair<int, int>> p;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (g[i][j] == '#') p.push_back({i, j});
        }
    }

    vector<int> xs, ys;
    for (auto [x, y] : p) {
        xs.push_back(x);
        ys.push_back(y);
    }
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    int cx = xs[1], cy = ys[1];

    auto paint = [&](int x, int y) {
        while (x != cx) {
            g[x][y] = '#';
            x += (x < cx ? 1 : -1);
        }
        while (y != cy) {
            g[x][y] = '#';
            y += (y < cy ? 1 : -1);
        }
        g[x][y] = '#';
    };

    for (auto [x, y] : p) paint(x, y);

    for (auto &s : g) cout << s << '\n';
    return 0;
}