AOJ1618: A Garden with Ponds

問題

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1618&lang=jp

問題概要

面倒なので省略

解答例

指針

  • 4重ループを回しすべての長方形について考える

解説

長方形の x の範囲 [lx, ry], y の範囲 [ly, ry] に関してループを回しすべての長方形について考える.

ある長方形を指定したときその長方形領域からなる池の容量を求めるには以下のようにする.

  • 長方形の一番外側のセルの中で最小のものを求める.

  • 内部のセルの中に外側のセルの中で最小のもの以上のものがあったら 0 を返し, なかったら池の容量を返す.

やるべきことは明確だが実装がやや面倒な問題.

計算量は長方形の選択に O(n4), 各々の長方形の容量を求めるのに各 O(n2) かかるので, 全体としては O(n6).

# coding: utf-8

def func(lx, rx, ly, ry, e):
    ret = 0
    soto_min = 0xdeadbeef

    # 長方形の一番外側のセルの中で最小のものを soto_min とする
    for i in range(lx, rx+1):
        for j in range(ly, ry+1):
            if i == lx or i == rx or j == ly or j == ry:
                soto_min = min(soto_min, e[j][i])

    # soto_min 以上のセルが内部にあったら 0 を返し, なかったら池の容量を返す.
    for i in range(lx, rx+1):
        for j in range(ly, ry+1):
            if i == lx or i == rx or j == ly or j == ry:
                continue

            if e[j][i] >= soto_min:
                return 0

            ret += (soto_min - e[j][i])

    return ret


while True:
    d, w = map(int, raw_input().split())

    if d == 0 and w == 0:
        break

    e = [map(int, raw_input().split()) for _ in range(d)]

    ans = 0

    # 長方形の x の範囲 [lx, ry], y の範囲 [ly, ry] に関してループを回す
    for lx in range(w-2):
        for rx in range(lx+2, w):
            for ly in range(d-2):
                for ry in range(ly+2, d):
                    ans = max(ans, func(lx, rx, ly, ry, e))

    print ans
  • C++ による実装例
#include <iostream>
#include <algorithm>

using namespace std;

int e[101][101];

int cal(int lx, int rx, int ly, int ry) {
    int ret = 0;
    int soto_min = 100;

    for (int i = lx; i <= rx; i++) {
        for (int j = ly; j <= ry; j++) {
            if (i == lx || i == rx || j == ly || j == ry) {
                soto_min = min(soto_min, e[j][i]);
            }
        }
    }

    for (int i = lx; i <= rx; i++) {
        for (int j = ly; j <= ry; j++) {
            if (i == lx || i == rx || j == ly || j == ry) { continue; }

            if (e[j][i] >= soto_min) { return 0; }

            ret += (soto_min - e[j][i]);
        }
    }
    return ret;
}

int main() {
    int d, w;

    while (cin >> d >> w) {
        if ( d == 0 && w == 0 ) { break; }

        for (int i = 0; i < d; i++) {
            for (int j = 0; j < w; j++) {
                cin >> e[i][j];
            }
        }
        int ans = 0;
        for (int lx = 0; lx < w-2; lx++) {
            for (int rx = lx+2; rx < w; rx++) {
                for (int ly = 0; ly < d-2; ly++) {
                    for (int ry = 0; ry < d; ry++) {
                        ans = max(ans, cal(lx, rx, ly, ry));
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}

参考文献