AOJ 1618 池のある庭園 (ICPC 国内予選 2017 C) (150 点)

この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない

• 問題へのリンク

問題概要

の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。

グリッド上で、以下の条件を満たす長方形領域を考える

• 縦の長さも横の長さも 3 以上
• 長方形の外周マスの数値の最小値 ( とする) は、長方形の外周を除いた内部マスの数値の最大値よりも大きい

この条件を満たす長方形領域のスコアを、長方形の各内部マスに対しての「 - マスの数値」の総和として定める。スコアの最大値を求めよ。ただし条件を満たす長方形領域が存在しない場合は 0 を出力せよ。

制約

• データセット数
• 

考えたこと

とにかく長方形領域を全探索する、 で間に合う。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int H, W;
    while (cin >> H >> W, H) {
        vector<vector<int>> fi(H, vector<int>(W));
        for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> fi[i][j];
        int res = 0;
        for (int il = 0; il < H; ++il) {
            for (int ir = il+3; ir <= H; ++ir) {
                for (int jl = 0; jl < W; ++jl) {
                    for (int jr = jl+3; jr <= W; ++jr) {
                        int mi = 10, ma = -1;
                        for (int i = il; i < ir; ++i) {
                            for (int j = jl; j < jr; ++j) {
                                if (i == il || i == ir-1 || j == jl || j == jr-1) {
                                    chmin(mi, fi[i][j]);
                                }
                                else chmax(ma, fi[i][j]);
                            }
                        }
                        if (ma < mi) {
                            int score = 0;
                            for (int i = il+1; i < ir-1; ++i) {
                                for (int j = jl+1; j < jr-1; ++j) {
                                    score += mi - fi[i][j];
                                }
                            }
                            chmax(res, score);
                        }
                    }
                }
            }
        }
        cout << res << endl;
    }
}