题解：P14572 「LAOI-11」Quest

Tipsy_bamboo · 2025-12-05 06:26:18 · 题解

这道题可以直接考虑确定选择方式。

我先来解释一下题目的意思，就是每个点出发，你可以横向走一步，也可以纵向走一步，但是不能连走两次横向或者纵向，最后走回到这个点，经过的点迹就是一个回路。

首先不难证明，一定有一个点 (x,y)，他的左边和上面，即 (x - 1, y) 和 (x, y- 1) 均不在要覆盖的点内。那么我们考虑这个点应该在哪个回路当中。

如果这个点下面的点 (x + 1,y) 不在要覆盖的点内，我们发现这个点只有一条出路，直接就是输出 -1。

那么如果下面的点在要覆盖的点内，我们需要取下面及右边的点构成回路。再分析右边的点，他不能取再右边的，因为这样就共线了，所以他只能取 (x + 1, y + 1)，这样我们发现，对于横着的一条连续的点，我们唯一确定了连接方式，即第 2k - 1 个点连接第 2k 个点，如果有单出来的，就是不合法。

最后对横向和纵向各跑一遍就可以得到连边方式，最后跑 dfs 输出方案即可。

代码如下

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

const int N = 1e6 + 5;

struct dot {
    int x, y, id;
};

vector <int> road[N];
vector <int> ans[N];
dot dots[N];
int vis[N], cnt;

bool cmp (dot a, dot b) {
    if (a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
}

bool cmp2 (dot a, dot b) {
    if (a.y == b.y) return a.x < b.x;
    else return a.y < b.y;
}

void dfs (int x) {
    vis[x] = 1, ans[cnt].push_back (x);
    for (auto i : road[x]) if (vis[i] == 0) dfs (i);
}

int main () {
    int n, l = 1, r = 0;
    cin >> n, dots[n + 1].x = dots[n + 1].y = INT_MAX;
    for (int i = 1; i <= n; ++i) cin >> dots[i].x >> dots[i].y, dots[i].id = i;
    sort (dots + 1, dots + 1 + n, cmp);
    while (r != n) {
        l = r + 1;
        while (dots[r + 1].x == dots[l].x) ++r;
        while (l < r) {
            if (l < r && dots[l].y + 1 == dots[l + 1].y) {
                road[dots[l].id].push_back (dots[l + 1].id), road[dots[l + 1].id].push_back (dots[l].id), l += 2;
            }
        }
        if (l == r) {
            cout << -1 << endl;
            return 0;
        }
    }
    sort (dots + 1, dots + 1 + n, cmp2), l = 1, r = 0;
    while (r != n) {
        l = r + 1;
        while (dots[r + 1].y == dots[l].y) ++r;
        while (l < r) {
            if (l < r && dots[l].x + 1 == dots[l + 1].x) {
                road[dots[l].id].push_back (dots[l + 1].id), road[dots[l + 1].id].push_back (dots[l].id), l += 2;
            }
        }
        if (l == r) {
            cout << -1 << endl;
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i) if (vis[i] == 0) ++cnt, dfs (i);
    cout << cnt << endl;
    for (int i = 1; i <= cnt; ++i) {
        cout << ans[i].size () << " ";
        for (auto j : ans[i]) cout << j << " ";
        cout << endl;
    }
    return 0;
}