题解：AT_abc232_h [ABC232H] King's Tour

· · 题解

Solution

神经病构造题。

题目没告诉你无解该咋办，所以肯定有解。所以我们可以直接做这样一个假设：给定任何一个 n \times m 的网格，可以从 (1,1) 走到 \forall (i,j) \neq (1,1)。

其他题解都是神秘构造，我们考虑归纳。也就是说，不断地让 n 或 m 减少 1，并且保证有解。

当 n 或 m 等于 2 时（归纳奠基），考虑证明一定有解。这个就是分类讨论几下就行：

当 n,m \ge 3 的时候，如果点离上或左（认为 (1,1) 在左上角）边界中的一个距离 \ge 2，就可以直接归纳。

否则，发现只剩下 (1,2)、(2,1)、(2,2)，还是能够直接归纳。

所以设 solve(n,m,px,py) 表示处理 n \times m 的矩形，从 (1,1) \to (px,py) 的一个解，返回路径。递归的时候旋转拼凑一下即可。

考虑分析一下复杂度。会递归 n+m 层，所以暴力复杂度为 O(n^3)，哎还行吧。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100+10;
int n,m,px,py; 
vector<pair<int,int>> solve(int n,int m,int px,int py) {
    if(n==2) {
        vector<pair<int,int>> ans;
        if(px==1&&py%2==0) {
            ans.push_back({1,1});
            ans.push_back({2,1});
            int tpos=2;
            while(tpos<py) ans.push_back({2,tpos}),ans.push_back({1,tpos}),tpos++,ans.push_back({1,tpos}),ans.push_back({2,tpos}),tpos++;
            ffor(i,tpos,m) ans.push_back({2,i});
            roff(i,m,tpos) ans.push_back({1,i});
        }
        else if(px==1&&py%2==1) {
            ans.push_back({1,1});
            ans.push_back({2,1});
            ans.push_back({1,2});
            ans.push_back({2,2});
            int tpos=3;
            while(tpos<py) ans.push_back({2,tpos}),ans.push_back({1,tpos}),tpos++,ans.push_back({1,tpos}),ans.push_back({2,tpos}),tpos++;
            ffor(i,tpos,m) ans.push_back({2,i});
            roff(i,m,tpos) ans.push_back({1,i});
        }
        else if(px==2&&py%2==0) {
            ans.push_back({1,1});
            ans.push_back({2,1});
            ans.push_back({1,2});
            int tpos=2;
            while(tpos<py) ans.push_back({2,tpos}),tpos++,ans.push_back({2,tpos}),ans.push_back({1,tpos}),tpos++,ans.push_back({1,tpos});   
            ffor(i,tpos+1,m) ans.push_back({1,i});
            roff(i,m,tpos) ans.push_back({2,i});
        }
        else {
            int tpos=1;
            ans.push_back({1,1});
            while(tpos<py) ans.push_back({2,tpos}),tpos++,ans.push_back({2,tpos}),ans.push_back({1,tpos}),tpos++,ans.push_back({1,tpos});
            ffor(i,tpos+1,m) ans.push_back({1,i});
            roff(i,m,tpos) ans.push_back({2,i});    
        }
        return ans;
    }
    else if(m==2) {
        auto vc=solve(m,n,py,px);
        ffor(i,0,vc.size()-1) swap(vc[i].first,vc[i].second);
        return vc;  
    }
    if(px>2||px==2&&py==2||px==2&&py==1) {
        vector<pair<int,int>> ans;
        auto vc=solve(n-1,m,px-1,m-py+1);
        ffor(i,1,m) ans.push_back({1,i});
        for(auto pr:vc) ans.push_back({pr.first+1,m-pr.second+1});
        return ans;
    }
    if(py>2||px==1&&py==2) {
        vector<pair<int,int>> ans;
        auto vc=solve(n,m-1,n-px+1,py-1);
        ffor(i,1,n) ans.push_back({i,1});
        for(auto pr:vc) ans.push_back({n-pr.first+1,pr.second+1});  
        return ans;
    }
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>px>>py;
    vector<pair<int,int>> ans=solve(n,m,px,py);
    for(auto pr:ans) cout<<pr.first<<' '<<pr.second<<'\n';
//  assert(st.size()==n*m&&ans.size()==n*m);
    return 0;
}