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).
- Python による実装例
# 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; }