CF1689D

王熙文 · 2022-07-25 11:15:33 · 题解

思路

其实拆开曼哈顿距离之后分讨也可以做，但是这里有一个更加无脑的做法：随机化。

考虑随机 500 个点，对于这些点找到其最远的 B 格子，然后枚举所有点计算与这些 B 格子的最远曼哈顿距离，取最小即可。

参考代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;

int n,m;

string s[1010];

pair<int,int> p[510];

int main()
{
    int t; cin>>t;
    while(t--)
    {
        int cnt=0;
        cin>>n>>m;
        for(int i=1; i<=n; ++i)
        {
            cin>>s[i]; s[i]=" "+s[i];
        }
        for(int i=1; i<=500; ++i)
        {
            int x=rand()%n+1,y=rand()%m+1;
            int ax=-1,ansx,ansy; // 注意，这里的 ax 不能设为 0，因为如果随机到的点恰好是唯一的一个 B，曼哈顿距离是 0，不能更新了
            for(int j=1; j<=n; ++j)
            {
                for(int k=1; k<=m; ++k)
                {
                    if(s[j][k]=='B')
                    {
                        if(abs(x-j)+abs(y-k)>ax)
                        {
                            ax=abs(x-j)+abs(y-k);
                            ansx=j,ansy=k;
                        }
                    }
                }
            }
            p[++cnt]={ansx,ansy};
        }
        sort(p+1,p+cnt+1);
        cnt=unique(p+1,p+cnt+1)-p-1;
        int in=1e9,ansx,ansy;
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; j<=m; ++j)
            {
                int nowax=0;
                for(int k=1; k<=cnt; ++k)
                {
                    nowax=max(nowax,abs(i-p[k].first)+abs(j-p[k].second));
                }
                if(nowax<in)
                {
                    in=nowax;
                    ansx=i,ansy=j;
                }
            }
        }
        cout<<ansx<<' '<<ansy<<'\n';
    }
    return 0;
}