[数据结构与算法]平面最短曼哈顿距离技巧 Dist Max、Lena and Matrix、Gojou and Matrix Game 三题题解

曼哈顿距离

曼哈顿距离是指对于两个点$a(i,j),b(i^{\prime },j^{\prime })$，它们的曼哈顿距离是$|i?i^{\prime }|+|j?j^{\prime }|$，记为$dis(a,b)$

我们显然可以做如下变化

$dis(a,b)=|i?i^{\prime }|+|j?j^{\prime }|=\max (i?i^{\prime },i^{\prime }?i)+\max (j?j^{\prime }.j^{\prime }?j)$

这是因为$abs$函数的性质，两个数一非正一非负，就相当于取$\max$

两个最大值，做笛卡尔积一共可以产生四种情况，加号可以直接拆开，得到

$\begin{array}{rl}dis(a,b)& =\max (i?i^{\prime }+j?j^{\prime },i?i^{\prime }+j^{\prime }?j,i^{\prime }?i+j?j^{\prime },i^{\prime }?i+j^{\prime }?j)\\ & =\max ((i+j)?(i^{\prime }+j^{\prime }),(i?j)?(i?j^{\prime }),?(i?j)+(i^{\prime }?j^{\prime }),?(i+j)+(i^{\prime }+j^{\prime }))\\ & =\max (|(i+j)?(i^{\prime }+j^{\prime })|,|(i?j)?(i?j^{\prime })|)\end{array}$

之后我们可以令$z_a=i+j,w_z=i?j,z_b=i^{\prime }+j^{\prime },w_b=i^{\prime }?j^{\prime }$，那么可以进一步化简为

$dis(a,b)=max(|z_a?z_b|,|w_a?w_b|)$

这就是一个另外表述的曼哈顿距离了。

平面最远曼哈顿距离

有什么用呢，比如我们要求一个点和一个点集的最大距离，那么相当于求$\max (\max (|z_i?z_x|,|w_i?w_x|))$。绝对值函数是很容易处理的，我们只需维护z的最大值最小值和w的最大值最小值就行了，那么最后答案应该是$max(z_{max}?z_x,z_x?z_{min},w_{max}?w_x,w_x?w_{min})$。扫一遍的复杂度是$O(n)$，假如拓展到点集和点集的最远距离或是最小最大距离等等，我们就只用维护一个枚举一个就好了，时间复杂度为$O(n)$。对于我们的标题“平面最远曼哈顿”，就扫一遍维护，在扫一遍枚举就行了。

一些例题

DIST Max（平面最远曼哈顿距离）

E - Dist Max (atcoder.jp)

思路

裸题，上面提到流程了。

代码

// ___________.__             _________                                   __   
// \__    ___/|  |__   ____  /   _____/__ __  ____   ____________   _____/  |_ 
//   |    |   |  |  \_/ __ \ \_____  \|  |  \/    \ /  ___/\____ \ /  _ \   __\
//   |    |   |   Y  \  ___/ /        \  |  /   |  \\___ \ |  |_> >  <_> )  |  
//   |____|   |___|  /\___  >_______  /____/|___|  /____  >|   __/ \____/|__|  
//                 \/     \/        \/           \/     \/ |__|                 
#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#include<bitset>
#include<functional>
#include<cassert>
#include<complex>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#ifdef THESUNSPOT
    #define de(i) cout<<#i<<": "<<i<<endl;
#else
    #define de(i) ;
#endif
#define int long long
//#define double long double
using namespace std;
    typedef long long ll;
    const int maxn=1000005;
    const int inf=0x3f3f3f3f3f3f3f3f;
    int n,m,k;
    void yes(){
        cout<<"YES"<<endl;
    }
    void no(){
        cout<<"NO"<<endl;
    }

    void solve(){
        cin>>n;
        int maxz=-inf,minz=inf,maxw=-inf,minw=inf;
        while(n--){
            int x,y;
            cin>>x>>y;
            maxz=max(maxz,x+y);
            minz=min(minz,x+y);
            maxw=max(maxw,x-y);
            minw=min(minw,x-y);
        }
        cout<<max(abs(maxz-minz),abs(maxw-minw))<<endl;
    }

    signed main(){
        IOS
        #ifdef THESUNSPOT
            auto st=clock();
            freopen("IO\\in.txt","r",stdin);
            freopen("IO\\out.txt","w",stdout);
        #endif

        int tn=1;
        while(tn--){
            solve();
        }
        #ifdef THESUNSPOT
            auto ed=clock();
            cout<<endl<<"time: "<<ed-st<<"ms."<<endl;
            srand(time(0));
            cout<<"version: "<<rand()%1000<<endl;
        #endif
    }		
    

Lena and Matrix（最大距离最小化）

Problem - D - Codeforces

思路

也是上面的思路，求一个位置，使得其到所有黑点最大距离最小，我们枚举位置，之后最大距离取min即可。

代码

// ___________.__             _________                                   __   
// \__    ___/|  |__   ____  /   _____/__ __  ____   ____________   _____/  |_ 
//   |    |   |  |  \_/ __ \ \_____  \|  |  \/    \ /  ___/\____ \ /  _ \   __\
//   |    |   |   Y  \  ___/ /        \  |  /   |  \\___ \ |  |_> >  <_> )  |  
//   |____|   |___|  /\___  >_______  /____/|___|  /____  >|   __/ \____/|__|  
//                 \/     \/        \/           \/     \/ |__|                 
#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#include<bitset>
#include<functional>
#include<cassert>
#include<complex>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#ifdef THESUNSPOT
    #define de(i) cout<<#i<<": "<<i<<endl;
#else
    #define de(i) ;
#endif
//#define double long double
using namespace std;
    typedef long long ll;
    const int maxn=1025;
    const int inf=0x3f3f3f3f;
    int n,m,k;
    int a[maxn][maxn];
    void solve(){
        cin>>n>>m;
        pair<int,int>ans;
        int mina=inf;
        string s;
        int zmax=-inf,zmin=inf;
        int wmax=-inf,wmin=inf;
        for(int i=1;i<=n;i++){
            cin>>s;
            for(int j=1;j<=m;j++){
                if(s[j-1]=='B'){
                    a[i][j]=1;
                    zmax=max(zmax,i+j);
                    zmin=min(zmin,i+j);
                    wmax=max(wmax,i-j);
                    wmin=min(wmin,i-j);
                }
                else{
                    a[i][j]=0;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int mm=-inf;
                int zz=i+j;
                int ww=i-j;
                mm=max({zmax-zz,zz-zmin,wmax-ww,ww-wmin});
                if(mm<mina){
                   // cout<<i<<' '<<j<<endl;
                   // cout<<mm<<endl;
                    mina=mm;
                    ans={i,j};
                }
            }
        }

        cout<<ans.first<<' '<<ans.second<<endl;
    }

    signed main(){
        IOS
        #ifdef THESUNSPOT
            auto st=clock();
            freopen("IO\\in.txt","r",stdin);
            freopen("IO\\out.txt","w",stdout);
        #endif

        int tn=1;
        cin>>tn;
        while(tn--){
            solve();
        }
        #ifdef THESUNSPOT
            auto ed=clock();
            cout<<endl<<"time: "<<ed-st<<"ms."<<endl;
            srand(time(0));
            cout<<"version: "<<rand()%1000<<endl;
        #endif
    }

Gojou and Matrix Game（简单博弈，最大距离）

Problem - E - Codeforces

思路

题意是，给一个n*n方阵，其权值各不同，每次落子可以获得权，每次落子不能放在上一次曼哈顿距离k以内，但是再往前就没有限制了。

轮流落子，输出任意位置i,j，先手胜利或是失败。

容易发现，先手落完子后，假如后手不能一步走到权更高的地方，一定是先手胜利，因为先手可以下回原地。

假如后手移动到了权更高的地方，则相当于颠倒了先手后手，可以相当于在那个权更高的地方继续行动。

基于我们上面说的，我们可以使用递推，先考虑权最大的，之后权小的就可以根据之前推出的大权的胜负来决定小权的正负。

倒推时考虑，假如当前位置能前往其他先手必胜态（注意移动后先后手转置），那么这个点就是必负态。因此我们在倒推时记录必胜态的状态，能到达，也就是要求存在一个必胜态，其距离大于k。反过来说，如果这个点到所有必胜态的距离全小于等于k，那么这个点一定也是必胜态。

到此一切都明朗了，我们只需要倒推维护上面提到的四个量，之后每次判断是否当前点到点集最大曼哈顿距离小于等于k即可。

代码

// ___________.__             _________                                   __   
// \__    ___/|  |__   ____  /   _____/__ __  ____   ____________   _____/  |_ 
//   |    |   |  |  \_/ __ \ \_____  \|  |  \/    \ /  ___/\____ \ /  _ \   __\
//   |    |   |   Y  \  ___/ /        \  |  /   |  \\___ \ |  |_> >  <_> )  |  
//   |____|   |___|  /\___  >_______  /____/|___|  /____  >|   __/ \____/|__|  
//                 \/     \/        \/           \/     \/ |__|                 
#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#include<bitset>
#include<functional>
#include<cassert>
#include<complex>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#ifdef THESUNSPOT
    #define de(i) cout<<#i<<": "<<i<<endl;
#else
    #define de(i) ;
#endif
#define int long long
//#define double long double
using namespace std;
    typedef long long ll;
    const int maxn=4000005;
    const int inf=0x3f3f3f3f3f3f3f3f;
    int n,m,k;
    void yes(){
        cout<<"YES"<<endl;
    }
    void no(){
        cout<<"NO"<<endl;
    }
    pair<int,int>p[maxn];
    void solve(){

        cin>>n>>k;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int t;
                cin>>t;
                p[t]={i,j};
            }
        }
        vector<string>ans(n+1,string(n,'G'));
        int zmax=-inf,zmin=inf,wmax=-inf,wmin=inf;
        for(int i=n*n;i;i--){
            int x=p[i].first,y=p[i].second;
            int zo=x+y,wo=x-y;
            if(i==n*n||max({zmax-zo,zo-zmin,wmax-wo,wo-wmin})<=k){
                ans[x-1][y-1]='M';
                zmax=max(zmax,x+y);
                zmin=min(zmin,x+y);
                wmax=max(wmax,x-y);
                wmin=min(wmin,x-y);
            }
        }
        for(int i=0;i<n;i++)   cout<<ans[i]<<endl;
    }

    signed main(){
        IOS
        #ifdef THESUNSPOT
            auto st=clock();
            freopen("IO\\in.txt","r",stdin);
            freopen("IO\\out.txt","w",stdout);
        #endif

        int tn=1;
        while(tn--){
            solve();
        }
        #ifdef THESUNSPOT
            auto ed=clock();
            cout<<endl<<"time: "<<ed-st<<"ms."<<endl;
            srand(time(0));
            cout<<"version: "<<rand()%1000<<endl;
        #endif
    }