yukicoder No.402 最も海から遠い場所

問題

No.402 最も海から遠い場所 - yukicoder

考察

チェビシェフ距離はあまり見慣れない名前ですが、自分を円の中心とした距離のようなものです。
海からチェビシェフ距離が一番遠いマスはどのような箇所でしょうか。

とある点を中心に、全方向になるべく距離を取れるところとなると、島の中で最大のサイズを持つ正方形の中心です。
答えとなるチェビシェフ距離は、floor(正方形の辺の長さ + 1) / 2で求まります(色々なサイズの正方形を書いてみるとわかります)。

最大の正方形を求めるには、以下のDPを使うと楽です。

  • 周囲の海を距離0とする
  • 左上からDPをする
    • 海であれば0
    • 陸であれば、左上・左・上の中で最小の距離 + 1
  • 距離の中で最大の値が最大の辺の長さ

左/上方向にある海との距離を更新してゆくようなイメージです。

以上の処理で答えが求まり、計算量は O(H * W)です。

実装上の工夫

周囲を海に囲まれているので、それをこちらで用意します。
配列のサイズは[H + 2][W + 2]になります。
ギリギリのことを考えなくて良くなり、処理が楽になります。

コード

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> field(H+2, "");
    stringstream ss;
    rep(i, W+2)
        ss << ".";
    field[0] = ss.str();
    field[H+1] = ss.str();
    rep(i, H) {
        cin >> field[i+1];
        field[i+1] = "." + field[i+1] + ".";
    }

    vvi ans(H+2, vi(W+2, 0));
    ans[0][0] = 0;

    int largest = 0;
    REP(i, 1, H+1) {
        REP(j, 1, W+1) {
            if(field[i][j] == '.')
                ans[i][j] = 0;
            else
                ans[i][j] = min(ans[i-1][j], min(ans[i][j-1], ans[i-1][j-1])) + 1;
            chmax(largest, ans[i][j]);
        }
    }

    cout << (largest + 1) / 2 << endl;
    
    return 0;
}