Codeforces 1087C - Connect Three

Codeforces 1087C - Connect Three

题解链接

https://lucien.ink


题目链接

http://codeforces.com/contest/1087/problem/C


题意

有三个人在网格中,三个人的坐标互不相同,初始时所有网格都是白色的,你可以把任意多个网格染成黑色,染成黑色的网格可以相互连通(四连通),问至少需要对多少个网格进行染色,使得三个人之间两两可达。


思路

不论三个人的位置是怎样的,一定能形成一个将三个人完全覆盖的最小的矩形,且一定是两个人位于矩形的一个对角,另一个人在矩形内部。所以直接按照曼哈顿路径去随便染色就可以。


实现

https://pasteme.cn/2803

#include <bits/stdc++.h>
struct Node {
    int x, y, index;
} node[7];
std::pair<int ,int> ans[int(1e6) + 7];
int cnt = 0;
int main() {
    for (int i = 1; i <= 3; i++) std::cin >> node[i].x >> node[i].y, node[i].index = i;
    std::sort(node + 1, node + 1 + 3, [](Node a, Node b) { return a.x < b.x; });
    int up = node[3].x, down = node[1].x, mid = node[2].x;
    std::sort(node + 1, node + 1 + 3, [](Node a, Node b) { return a.y < b.y; });
    for (int i = node[1].y; i <= node[3].y; i++) ans[++cnt] = std::make_pair(mid, i);
    for (int i = 1; i <= 3; i++) {
        if (node[i].x != mid) {
            for (int j = std::min(mid, node[i].x), upper = std::max(mid, node[i].x); j <= upper; j++)
                ans[++cnt] = std::make_pair(j, node[i].y);
        }
    }
    std::sort(ans + 1, ans + cnt + 1);
    cnt = int(std::unique(ans + 1, ans + 1 + cnt) - ans - 1);
    std::printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++) std::printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}
最后修改:2018 年 12 月 24 日 01 : 15 AM
谢谢老板!

发表评论