题面大意
在 \(n\times m\) 的网格中构造一种从 \((1,1)\) 走到 \((a,b)\) 的方案，要求经过所有格子恰好一次，格子之间八联通。
思路分析
模拟赛题，赛时写了一个半小时过了（
思路不是很复杂，但是需要一些分类讨论。
-
引理：对于任意大小的矩形，一定存在从左上走到右下的方案。
-
证明：
若长宽中有一个是奇数，那么我们可以按照如下方案构造：
否则，我们可以按照如下方案构造：
那么同理，我们只需要将矩形翻转就可以得到从矩形一个角走到对角的方案。
设 walk(x1,y1,x2,y2) 表示输出从 \((x_1,y_1)\) 走到 \((x_2,y_2)\)，填满以 \((x_1,y_1)\) 和 \((x_2,y_2)\) 作为对角线的矩形的方案。
而当我们考虑从 \((1,1)\) 走到 \((a,b)\) 时，我们进行分类讨论，下面是图示和代码实现：
（蓝色边表示用引理的方案填满整个矩形，绿色边表示实际走的边。）
- \(a=n,b=m\)：
walk(1, 1, a, b)
- \(a=1,b=m\)：
walk(1, 1, n, m - 1);
walk(n, m, a, b);
- \(a=n,b=1\)：
walk(1, 1, n - 1, m);
walk(n, m, a, b);
- \(a=1,b\not =m\)：
walk(1, 1, n, b - 1);
walk(n, b, 2, m);
walk(1, m, a, b);
- \(b=1,a\not =n\)：
walk(1, 1, a - 1, m);
walk(a, m, n, 2);
walk(n, 1, a, b);
- \(a=n,b\not =1\)：
walk(1, 1, n, b - 1);
walk(n - 1, b, 1, b);
walk(1, b + 1, n - 1, m);
walk(n, m, a, b);
- \(b=m,a\not =1\)：
walk(1, 1, a - 1, m);
walk(a, m - 1, n - 1, 1);
walk(n, 1, n, m);
walk(n - 1, m, a, b);
- \(a\in[2,n-1],b\in[2,m-1]\)：
walk(1, 1, a - 1, m);
walk(a, m, n, b + 1);
walk(n, b, a + 1, 1);
walk(a, 1, a, b);
那么这题就愉快的结束了，时间复杂度显然是 \(O(n^2)\)。
代码
（109 行，3.5k）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int N = 200200;
#define inf 0x3f3f3f3f
int n, m, a, b;
namespace SOL{
void walk(int x1, int y1, int x2, int y2){
int dir;
if (x1 <= x2 && y1 <= y2) dir = 1;
if (x1 > x2 && y1 <= y2) dir = 3;
if (x1 <= x2 && y1 > y2) dir = 2;
if (x1 > x2 && y1 > y2) dir = 4;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
int n = x2 - x1 + 1, m = y2 - y1 + 1;
vector <pair<int, int>> v;
if ((n & 1) || (m & 1)) {
if (n & 1) {
int x = 1, y = 0, d = 1;
for (int i = 1; i <= n * m; i ++) {
y += d;
if (y == m + 1) y = m, x ++, d = -d;
if (y == 0) y = 1, x ++, d = -d;
v.push_back({x, y});
}
}
else {
int x = 0, y = 1, d = 1;
for (int i = 1; i <= n * m; i ++) {
x += d;
if (x == n + 1) x = n, y ++, d = -d;
if (x == 0) x = 1, y ++, d = -d;
v.push_back({x, y});
}
}
}
else {
int x = 1, y = 0, d = 1;
for (int i = 1; i <= (n - 2) * m; i ++) {
y += d;
if (y == m + 1) y = m, x ++, d = -d;
if (y == 0) y = 1, x ++, d = -d;
v.push_back({x, y});
}
for (int i = 1; i <= m; i ++) {
v.push_back({n - 1, i});
v.push_back({n, i});
}
}
if (dir == 2) for (auto &it : v) it.second = m - it.second + 1;
if (dir == 3) for (auto &it : v) it.first = n - it.first + 1;
if (dir == 4) for (auto &it : v) it.first = n - it.first + 1, it.second = m - it.second + 1;
for (auto it : v) cout << it.first + x1 - 1 << ' ' << it.second + y1 - 1 << '\n';
}
void work(){
if (a == n && b == m) {
walk(1, 1, n, m);
}
else if (a == n && b == 1) {
walk(1, 1, n - 1, m);
walk(n, m, a, b);
}
else if (a == 1 && b == m) {
walk(1, 1, n, m - 1);
walk(n, m, a, b);
}
else if (a == 1) {
walk(1, 1, n, b - 1);
walk(n, b, 2, m);
walk(1, m, a, b);
}
else if (b == m) {
walk(1, 1, a - 1, m);
walk(a, m - 1, n - 1, 1);
walk(n, 1, n, m);
walk(n - 1, m, a, b);
}
else if (a == n) {
walk(1, 1, n, b - 1);
walk(n - 1, b, 1, b);
walk(1, b + 1, n - 1, m);
walk(n, m, a, b);
}
else if (b == 1) {
walk(1, 1, a - 1, m);
walk(a, m, n, 2);
walk(n, 1, a, b);
}
else {
walk(1, 1, a - 1, m);
walk(a, m, n, b + 1);
walk(n, b, a + 1, 1);
walk(a, 1, a, b);
}
}
}
int main(){
scanf("%d %d %d %d", &n, &m, &a, &b);
return SOL::work(), 0;
}