Hihocoder #1042 跑馬圈地：枚舉矩形面積避開水塘

問題描述

n×m 網格，矩形水塘 [l,r]×[t,b]。繞行周長 ≤ L 的封閉折線（沿網格邊），不進入水塘。求最大圈地面積（不含水塘）。n,m≤100, L≤400。

關鍵觀察

最優路徑為軸向矩形（或切角矩形）。因周長固定，面積最大化趨向正方形。水塘位置可通過坐標變換統一到右上角（鏡像對稱）。

三種情況枚舉

1. 圈地不含水塘：面積 = w*h。
2. 圈地含水塘一頂點：面積 = w*h - (w-l)*(h-b)。
3. 圈地全含水塘：面積 = w*h - (r-l)*(t-b)。

枚舉寬 w、高 h，滿足 2*(w+h) ≤ L，按水塘相對位置計算面積，取最大值。

坐標變換統一水塘到右上角

int l1=l, r1=r, t1=t, b1=b;
if (l+r <= m) { l1=m-r; r1=m-l; } // 水塘在左半部 → 鏡像到右
if (t+b <= n) { t1=n-b; b1=n-t; } // 水塘在下半部 → 鏡像到上

代碼實現

int ans=0;
for (int w=1; w<=L/2 && w<=m; w++)
  for (int h=1; h<=L/2-w && h<=n; h++) {
    if (w<=l1 || h<=b1) ans=max(ans, w*h);
    else if (w<=r1 && h<=t1) ans=max(ans, w*h - (w-l1)*(h-b1));
    else if (w>=r1 && h>=t1) ans=max(ans, w*h - (r-l)*(t-b));
  }
cout<