AOJ 2953 Hokkaido University Hard (HUPC 2019 day2-B)

テスターだった。
簡単枠の Easy ヴァージョンに対して「制約あげられるね」と提案して、正式に問題セットになった！

• 問題へのリンク
• editorial

問題概要

のグリッドがあって、各マスは '.' か 'B' から成っている。'B' マス間のマンハッタン距離として考えられる最大値を求めよ。

制約

• 

考えたこと

2 点 に対して、

• となっているときは、 と式変形できる
  • このとき、この値は よりも大きい
• となっているときは、 と式変形できる
  • このとき、この値は よりも大きい

以上から、次のうちの最大値を求めれば OK。

• 各 B マス (x, y) についての、x + y の最大値と最小値の差
• 各 B マス (x, y) についての、x - y の最大値と最小値の差

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    int minS = H+W, maxS = 0, minD = H+W, maxD = -H-W;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (fi[i][j] != 'B') continue;
            minS = min(minS, i + j);
            maxS = max(maxS, i + j);
            minD = min(minD, i - j);
            maxD = max(maxD, i - j);
        }
    }
    cout << max(maxS - minS, maxD - minD) << endl;
}