PKU 3679 The Delivery of Control

題意：

給定 H x W 帶號整數二維陣列 (H, W ≤ 20)
現在要在其中走一個圈，周界 ≤ K (≤ 20)
（路線是 grid 的 edge，每走一條周界 += 1）
圈不可以 self-touch
計算被包圍的元素值的總和

求最大總和

---

不合法 shape 的樣例：

• 需要連接
  
• ◎　◎
• 不可以角碰角
• ◎◎
  ◎　◎
  ◎◎◎
• 剛剛才想到：角碰角 ⇒ 有洞
  所以不需要另寫程序作處理
  
• 不可以有洞 1 (周界 = 16)
  
• ◎◎◎
  ◎　◎
  ◎◎◎
• 不可以有洞 2 (周界 = 20)
  
• ◎◎◎
  ◎　◎
  ◎　◎
  ◎◎◎
  

---

昨晚（強迫）Leo 及 Chin 跟我討論這條比較少人AC 的題目

然後今天下午... 和 Joe 分別起手 code...
慶幸是挑戰成功了（雖然非常懷疑自己是水過）

嗯... 看見 range 及 10秒 時限 便想到 Searching 吧...

不過起初我還妄想能否用狀態 DP 解決
然後被一大堆不知怎麼處理的狀況解決了... orz
（當然，我不排除 DP 的可行性...）

所以只好 code 搜索

---

算法 - Idea：

這道題是屬於 "就是做" 的類別

就我認知範圍，可行的算法只有一種：

1. 先 generate 所有合法的 shape
2. 再枚舉所有位置，找出 Maximum
   

---

算法 ─ 概覽：

1. 生成所有合法 shape
   
   1. 在 W、H、K 的限制下，枚舉 bounding rectangle 的 長+闊
      
   2. 逐 column、 逐 row 深索，生成所有 shape - O(2^長×闊)
      
   3. 對 Shape 判斷合法性 - O(長×闊)
      若果合法，以 int 表示該 shape，記錄進陣列 int shapeArray[長][闊][周界][]
2. 對每種 Shape，枚舉所有可能位置，統計 Maximum - O(方法數×H×W×25)

---

Bounding Rectangle：

留意 shape 周界 ≥ bounding rectangle 的周界
⇒ bounding rectangle 的周界 ≤ K

所以我們可以枚舉 bounding rectangle 的 長和闊
──限制： (長 + 闊) × 2 ≤ K

嗯... 數量不算太多
"只有" 1 × 1, 1 × 2, ... 1 × 9, 2 × 2, ... 5 × 5, ... 9 × 1

45種?!... 放心，加些少剪枝就可以確保在時限內跑完！（好似係）

---

枚舉 Shape - 深搜：

（如上面所述）先枚舉長及闊
然後逐個元素（逐 column 逐 row）深搜
決定是否包含它（2種選擇）

這樣，我們便可以窮舉 O(2^長×闊) 種 shape

在深搜至到底時，再判斷該 shape 是否合法
本人的做法用 flood fill 判斷合法性

• shape 的連接性
• 檢查是否沒有洞存在

──這步驟比較慢呢... 但我想不出判合法的 incremental 方法

void dfs(int bitCode, int shape, int perimeter, int minRow, int maxRow);

最後，我們可以用一個 int 表示每一個 shape

──bounding rectangle 最多只有 25 格，25-bit 便足夠矣

將之記錄至：

int shapeArray[width][height][perimeter][numShape];

---

深搜 - 剪枝：

程序添加以下 Optimization：

1. 在搜索完一個 column，該 column 至少要有一項元素，否則 return
2. 記錄包含的元素之中， row id 最小 (minRow) 及 最大 (maxRow) 的一個；每次深搜至底，當 minRow = 0 及 maxRow = H-1 才檢查 shape 的合法性
   
3. 在深搜過程 O(1) 更新周界 (+= 4 - neighbor數目 × 2)，若周界超出 K 則 return
   ──因為周界只會變長或不變

---

Shape 的數量：

我的程序沒有考慮 rotationally / reflectively equivalent 的 shape
那就是說 ，反射／旋轉對稱的 shape 會分別被記錄

(H, W, K)	合法 Shape 的個數
(20, 20, 20)	100792 - 2
(20, 20, 18)	18965

因為數據比較水，本人對數字準確性有所保留...

---

運行時間：

(H, W, K)	生成所有合法 Shape	統計 Maximum
(20, 20, 20)	1.304 秒	5.539 秒
(20, 20, 18)	0.383 秒	1.085 秒

---

Test Data：

貌似 PKU 的 數據比較水，即使忽略以下情況仍能通過：

3 4 20
10 10 10 10
10 -1 -1 10
10 10 10 10

正解：98
錯解：100

---

延伸：

其實要加快，減省記憶及時間
可以如 Hackson 般 ，把 shape normalize w.r.t. translation / rotation / reflection
用 BFS generate 所有 shape
每次 dequeue 時，將已有的 shape 增廣一格，推入 queue 中
再用 Hash table 記錄訪問
不過這需要大量的 code...

另外，或者可以考慮利用表格元素值剪枝
不過一時間想不出比較簡便的剪枝...