题解：P15128 [ROIR 2026] 跛脚国王
前排提醒：因为作者太区了，所以构造很劣，勿喷qwq。
首先，若格子数为奇数，黑白染色后，构造出的路径，必定会有两个格子相同颜色，所以先判掉。
考虑以下基本构造（要求行数为偶数，不满足的可以旋转过来）
若两个格子为横向排列，则上述构造（或其左右翻转）一定能覆盖到。
若两个格子为纵向排列的情况，若其靠近边线，则上述构造（或其左右翻转）一定能覆盖到。
接下来考虑这种情况
这种情况在列数为
这种只需要走到对应点的时候强制拐弯，回来的时候把剩下的走了就行，如图所示
接下来考虑这种情况
这种情况在行数为
考虑先把限制走完，然后剩下再用前面的构造。
:::success[AC Code] 如果用封装可能会更短。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int n, m, flg;
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
} p1, p2;
vector<Point> vec;
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> p1.x >> p1.y >> p2.x >> p2.y;
if (n * m & 1) {
cout << -1 << '\n';
return 0;
}
if (m & 1 || ~n & 1 && n < m) {
flg = 1;
swap(n, m);
swap(p1.x, p1.y);
swap(p2.x, p2.y);
}
if (make_pair(p1.x, p1.y) > make_pair(p2.x, p2.y)) {
swap(p1, p2);
}
if (p1.y == p2.y) {
if (p1.x != 1) {
vec.emplace_back(1, 1);
for (int i = 1; i <= m; i += 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i; -- i) {
vec.emplace_back(1, i);
}
} else {
vec.emplace_back(n, 1);
for (int i = 1; i <= m; i += 2) {
for (int j = n - 1; j; -- j) {
vec.emplace_back(j, i);
}
for (int j = 1; j < n; ++ j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i; -- i) {
vec.emplace_back(n, i);
}
}
} else {
if (m == 2) {
if (p1.x == 1 || p1.x == n) {
vec.emplace_back(1, 1);
for (int i = 1; i <= n; ++ i) {
vec.emplace_back(i, 2);
}
for (int i = n; i; -- i) {
vec.emplace_back(i, 1);
}
} else {
cout << -1 << '\n';
return 0;
}
} else {
if (p1.x == 1) {
if (p1.y != 1) {
vec.emplace_back(1, 1);
for (int i = 1; i <= m; i += 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i; -- i) {
vec.emplace_back(1, i);
}
} else {
vec.emplace_back(1, m);
for (int i = m; i; i -= 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i - 1);
}
}
for (int i = 1; i <= m; ++ i) {
vec.emplace_back(1, i);
}
}
} else if (p1.x == n) {
if (p1.y != 1) {
vec.emplace_back(n, 1);
for (int i = 1; i <= m; i += 2) {
for (int j = n - 1; j; -- j) {
vec.emplace_back(j, i);
}
for (int j = 1; j < n; ++ j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i; -- i) {
vec.emplace_back(n, i);
}
} else {
vec.emplace_back(n, m);
for (int i = m; i; i -= 2) {
for (int j = n - 1; j; -- j) {
vec.emplace_back(j, i);
}
for (int j = 1; j < n; ++ j) {
vec.emplace_back(j, i - 1);
}
}
for (int i = 1; i <= m; ++ i) {
vec.emplace_back(n, i);
}
}
} else {
if (~p1.y & 1) {
vec.emplace_back(1, 1);
for (int i = 1; i <= p1.y - 2; i += 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = 2; i <= n; ++ i) {
vec.emplace_back(i, p1.y - 1);
}
for (int i = n; i >= p1.x; -- i) {
vec.emplace_back(i, p1.y);
}
for (int i = p2.x; i <= n; ++ i) {
vec.emplace_back(i, p2.y);
}
for (int i = n; i > 1; -- i) {
vec.emplace_back(i, p2.y + 1);
}
for (int i = p2.y + 2; i <= m; i += 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i > p2.y; -- i) {
vec.emplace_back(1, i);
}
for (int i = 1; i < p2.x; ++ i) {
vec.emplace_back(i, p2.y);
}
for (int i = p1.x - 1; i; -- i) {
vec.emplace_back(i, p1.y);
}
for (int i = p1.y - 1; i; -- i) {
vec.emplace_back(1, i);
}
} else {
if (p2.y != m) {
if (p2.x != 2) {
vec.emplace_back(1, 1);
for (int i = 1; i <= p2.y; i += 2) {
for (int j = 2; j < p1.x; ++ j) {
vec.emplace_back(j, i);
}
for (int j = p1.x - 1; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = 2; i < p1.x; ++ i) {
vec.emplace_back(i, p2.y + 1);
}
for (int i = p2.y + 1; i; -- i) {
vec.emplace_back(p1.x, i);
}
for (int i = 1; i <= p2.y; i += 2) {
for (int j = p1.x + 1; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > p1.x; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = p1.x + 1; i <= n; ++ i) {
vec.emplace_back(i, p2.y + 1);
}
for (int i = n; i > 1; -- i) {
vec.emplace_back(i, p2.y + 2);
}
for (int i = p2.y + 3; i <= m; i += 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i; -- i) {
vec.emplace_back(1, i);
}
} else {
if (n <= 3) {
cout << -1 << '\n';
return 0;
}
vec.emplace_back(1, 1);
for (int i = 1; i <= p2.y + 1; ++ i) {
vec.emplace_back(2, i);
}
for (int i = p2.y + 1; i; -- i) {
vec.emplace_back(3, i);
}
for (int i = 1; i <= p2.y; i += 2) {
for (int j = 4; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 3; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = p1.x + 2; i <= n; ++ i) {
vec.emplace_back(i, p2.y + 1);
}
for (int i = n; i > 1; -- i) {
vec.emplace_back(i, p2.y + 2);
}
for (int i = p2.y + 3; i <= m; i += 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i + 1);
}
}
for (int i = m; i; -- i) {
vec.emplace_back(1, i);
}
}
} else {
if (p2.x != 2) {
vec.emplace_back(1, m);
for (int i = m; i >= p1.y; i -= 2) {
for (int j = 2; j < p1.x; ++ j) {
vec.emplace_back(j, i);
}
for (int j = p1.x - 1; j > 1; -- j) {
vec.emplace_back(j, i - 1);
}
}
for (int i = 2; i < p1.x; ++ i) {
vec.emplace_back(i, p1.y - 1);
}
for (int i = p1.y - 1; i <= m; ++ i) {
vec.emplace_back(p1.x, i);
}
for (int i = m; i >= p1.y; i -= 2) {
for (int j = p1.x + 1; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > p1.x; -- j) {
vec.emplace_back(j, i - 1);
}
}
for (int i = p1.x + 1; i <= n; ++ i) {
vec.emplace_back(i, p1.y - 1);
}
for (int i = n; i > 1; -- i) {
vec.emplace_back(i, p1.y - 2);
}
for (int i = p1.y - 3; i; i -= 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i - 1);
}
}
for (int i = 1; i <= m; ++ i) {
vec.emplace_back(1, i);
}
} else {
vec.emplace_back(1, m);
for (int i = m; i >= m - 2; -- i) {
vec.emplace_back(2, i);
}
for (int i = m - 2; i <= m; ++ i) {
vec.emplace_back(3, i);
}
for (int i = 4; i <= n; ++ i) {
vec.emplace_back(i, m);
}
for (int i = n; i > 3; -- i) {
vec.emplace_back(i, m - 1);
}
for (int i = 4; i <= n; ++ i) {
vec.emplace_back(i, m - 2);
}
for (int i = n; i > 1; -- i) {
vec.emplace_back(i, m - 3);
}
for (int i = m - 4; i; i -= 2) {
for (int j = 2; j <= n; ++ j) {
vec.emplace_back(j, i);
}
for (int j = n; j > 1; -- j) {
vec.emplace_back(j, i - 1);
}
}
for (int i = 1; i <= m; ++ i) {
vec.emplace_back(1, i);
}
}
}
}
}
}
}
if (flg) {
for (auto &[x, y] : vec) {
swap(x, y);
}
}
for (auto [x, y] : vec) {
cout << x << ' ' << y << '\n';
}
return 0;
}:::