---
# System prepended metadata

title: D. Lena and Matrix

---

# D. Lena and Matrix

link : https://codeforces.com/problemset/problem/1689/D

tóm tắt đề : cho bảng 2D có 2 loại ô, W và B, tìm ô thỏa mãn max khoảng cách mahatan tới các ô B là min

ý tưởng : xoay bảng 45 độ

code AC : 

:::spoiler
```cpp=
#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)
#define ll long long

using namespace std;
int n, m;
string a[1001];

int cost(int x, int y)
{
    if (x > n || x < 1 || y > m || y < 1) return 2001;
    int t = 0;
    rep(i, 1, n) rep(j, 1, m) if (a[i][j - 1] == 'B')
        t = max(t, abs(x - i) + abs(y - j));

    return t;
}

int main(){
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);

    int t; cin >> t;
    while(t--)
    {
        int mix, mxx, miy, mxy;
        mix = miy = 10000000;
        mxx = mxy = -10000000;
        cin >> n >> m;
        rep(i, 1, n)
        {
            cin >> a[i];
            rep(j, 1, m) if (a[i][j - 1] == 'B')
            {
                mix = min(mix, i + j);
                mxx = max(mxx, i + j);
                miy = min(miy, i - j);
                mxy = max(mxy, i - j);
            }
        }

        int x = (mix + mxx + 1)/2, y = (miy + mxy + 1)/2;
        int xx = (x + y)/2, yy = (x - y)/2;
        x = xx; y = yy;
        int best = cost(x, y);
        rep(i, -8, 8) rep(j, -8, 8) if (best > cost(x + i, y + j))
        {
            best = cost(x + i, y + j);
            xx = x + i;
            yy = y + j;
        }
        cout << xx << ' ' << yy << endl;
    }
}
```
:::