题解：P15128 [ROIR 2026] 跛脚国王

zhangyuhaoaa · 2026-10-19 19:07:08 · 题解

发现这是一道分类讨论的题目，可以分一下四种情况，分别是：

然后把这些情况旋转四次就可以有了所有的情况。

代码如下：

// Problem: B. 跛脚国王（king）
// Contest: Hydro
// URL: http://192.168.9.119/d/wfbcoi/p/49?tid=6ad563ab9bc6880c716f1afc
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
// #define int long long
#define endl "\n"
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

const int P = 998244353;
const int INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 1e3 + 5;

int n, m;
int xa, ya, xb, yb;
int a[maxn][maxn];

pair<int, int> get(pair<int, int> p, int t) {
  int x = p.first, y = p.second;
  if (t & 1) x = n + 1 - x;
  if (t & 2) y = m + 1 - y;
  return {x, y};
}

void check(const vector<pair<int, int> >& res, int fl) {
  for (int t = 0; t < 4; ++ t ) {
    int flg = 0;
    for (int i = 1; i < res.size(); ++ i ) {
      auto a = get(res[i - 1], t), b = get(res[i], t);
      if ((a.first == xa && a.second == ya && b.first == xb && b.second == yb) ||
          (a.first == xb && a.second == yb && b.first == xa && b.second == ya)) {
        flg = 1;
        break;
      }
    }
    if (flg == 1) {
      for (auto e : res) {
        auto p = get(e, t);
        if (fl == 0) cout << p.first << " " << p.second << "\n";
        else cout << p.second << " " << p.first << "\n";
      }
      exit(0);
    }
  }
}

void work1(int flag) {
  vector<pair<int, int> > res;
  res.push_back({1, 1});
  for (int i = 1, flg = 1; i <= n; ++ i, flg = -flg ) {
    if (flg == 1) for (int j = 2; j <= m; ++ j ) res.push_back({i, j});
    else for (int j = m; j >= 2; -- j ) res.push_back({i, j});
  }
  for (int i = n; i >= 1; -- i ) res.push_back({i, 1});
  check(res, flag);
  res.clear();
  res.push_back({1, 1});
  for (int i = 2, flg = 1; i <= n; ++ i, flg = -flg ) {
    if (flg == 1) for (int j = 1; j <= m - 1; ++ j ) res.push_back({i, j});
    else for (int j = m - 1; j >= 1; -- j ) res.push_back({i, j});
  }
  for (int i = n; i >= 1; -- i ) res.push_back({i, m});
  for (int i = m - 1; i >= 1; -- i ) res.push_back({1, i});
  check(res, flag);
}
void work2(int flag) {
  vector<pair<int, int> > res;
  res.push_back({1, 1});
  for (int i = 2, flg = 1; i <= m; ++ i, flg = -flg ) {
    if (flg == 1) res.push_back({1, i}), res.push_back({2, i});
    else res.push_back({2, i}), res.push_back({1, i});
  }
  for (int i = 3, flg = 1; i <= n; ++ i, flg = -flg ) {
    if (flg == 1) for (int j = m; j >= 2; -- j ) res.push_back({i, j});
    else for (int j = 2; j <= m; ++ j ) res.push_back({i, j});
  }
  for (int i = n; i >= 1; -- i ) res.push_back({i, 1});
  check(res, flag);
  res.clear();
  res.push_back({1, 1});
  for (int i = 1, flg = 1; i <= n - 2; ++ i, flg = -flg ) {
    if (flg == 1) for (int j = 2; j <= m; ++ j ) res.push_back({i, j});
    else for (int j = m; j >= 2; -- j ) res.push_back({i, j});
  }
  for (int i = m, flg = 1; i >= 2; -- i, flg = -flg ) {
    if (flg == 1) res.push_back({n - 1, i}), res.push_back({n, i});
    else res.push_back({n, i}), res.push_back({n - 1, i});
  }
  for (int i = n; i >= 1; -- i ) res.push_back({i, 1});
  check(res, flag);
}

signed main() {
  //system("fc .out .out");
  // freopen("king.in","r",stdin);
  // freopen("king.out","w",stdout);
  fst;

  cin >> n >> m;
  cin >> xa >> ya >> xb >> yb;
  if (n % 2 == 1 && m % 2 == 1) return cout << -1, 0;
  if (n == 2) {
    if (min(ya, yb) != 1 && max(ya, yb) != m && abs(xa - xb) == 1) return cout << -1, 0;
    for (int i = 1; i <= m; ++ i ) cout << 1 << " " << i << endl;
    for (int i = m; i >= 1; -- i ) cout << 2 << " " << i << endl;
    cout << 1 << " " << 1 << endl;
    return 0;
  } else if (m == 2) {
    if (min(xa, xb) != 1 && max(xa, xb) != n && abs(ya - yb) == 1) return cout << -1, 0;
    for (int i = 1; i <= n; ++ i ) cout << i << " " << 1 << endl;
    for (int i = n; i >= 1; -- i ) cout << i << " " << 2 << endl;
    cout << 1 << " " << 1 << endl;
    return 0;
  }
  if (n % 2 == 0) work1(0);
  else work2(0);
  if (m % 2 == 0) {
    swap(n, m), swap(xa, ya), swap(xb, yb);
    work1(1);
  } else {
    swap(n, m), swap(xa, ya), swap(xb, yb);
    work2(1);
  }
  cout << -1;

  return 0;
}

代码太难看了，不建议看。