【题解】 CF1689D Lena and Matrix

· · 题解

D. Lena and Matrix

博客食用效果更佳

题目描述

原题面

给定一个 n\times m 的矩阵，每个位置都有一个颜色，分别为黑色或白色，要求你选择一个位置（不计这个位置上是什么颜色），使得这个位置到所有黑色格子的曼哈顿距离的最大值最小。

曼哈顿距离即：|x_1 - x_2| + |y_1 - y_2|

题目分析

要求的是最大值最小，其实发现这个最大值不是和任意一个黑色格子的距离都有可能成为最大值的，能成为最大距离的黑色格子一定是最左上、右下、左下、右上的黑格子，可以发现如果不是这四个格子，那么把距离转化到这四个黑色格子上都一定可以增加。

下面就是如何寻找着四个黑色格子的问题了，我感觉这个思路还是很神奇的。

考虑如果一个格子离左上角越近，x 越小，y 越小，而且 x 与 y 的减小，对其离左上角的距离产生的贡献是一样的，那么就直接令这个贡献为 x+y，那么最左上角的点也就一定是贡献最小的点，最右下角的点也一定是贡献最大的点，这就解决了两个。

考虑如果一个格子里右上角越近，x 越大，y 越小，而且它们产生的贡献也都是一样的，所以就考虑直接令贡献为 x-y，这样最右上的点也就是 x-y 最大点，最左下的点也就是 x-y 最小的点，至此四个点全部解决了。

那么就是要找一个位置使得这个位置到这四个位置的距离最大值最小，那么就直接枚举每一个位置寻找一下就好了。

代码详解

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
struct node{
    int x,y;
    node(){}
    node(int _x,int _y){
        x = _x,y = _y;
    }
};
int main(){
    int t;
    cin>>t;
    while(t--){
        node a[6];
        bool flag[6];
        memset(flag,0,sizeof(flag));
        int n,m;
        cin>>n>>m;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                char h;
                cin>>h;
                if(h == 'B'){
                    if(i + j > a[1].x + a[1].y || !flag[1]) a[1] = node(i,j),flag[1] = true;
                    //越在右下角 i + j 越大 
                    if(i + j < a[2].x + a[2].y || !flag[2]) a[2] = node(i,j),flag[2] = true;
                    //越在左上角 i + j 越小 
                    if(i - j > a[3].x - a[3].y || !flag[3]) a[3] = node(i,j),flag[3] = true;
                    //越在右上角 i - j 越大 
                    if(i - j < a[4].x - a[4].y || !flag[4]) a[4] = node(i,j),flag[4] = true;
                    //越在左下角 i - j 越小 
                }
            }
        }
        int res = INF;
        node ans;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                int h = 0;
                for(int k=1; k<=4; k++){
                    h = max(h,abs(i - a[k].x) + abs(j - a[k].y));
                }
                if(h < res){
                    ans = node(i,j);
                    res = h;    
                }
            }
        }
        printf("%d %d\n",ans.x,ans.y);
    }
    return 0;
}

先去找四个点找到了就每个位置枚举一下，最后输出就好了。