959 . 農田劃分
TopCoder
Tags
Description
來自童話村的七誠與七南是一對兄弟，最近他們正攜手合作開墾一塊農田。這塊農田的高度為 $H$、寬度為 $W$，被劃分為 $1 \times 1$ 的單位格。
兩人對於農田的規劃方式有不同的堅持：
- 七誠認為作物的種類不宜太多，因此整塊農田中作物種類不超過 $5$ 種，而且他已經為每一種作物指定了應種植的面積大小。
- 七南則希望作業能夠簡單施行，因此他要求同一種作物必須被種植在一個矩形區塊中，也就是說，每種作物只能對應到一個連續的矩形區域。
此外，七誠還事先標註了一些特殊地塊，每一塊特殊地都對應到一種作物，並標示了該作物所需分配的面積。
例如下圖所示，七誠在農田中圈出了幾塊作物的特殊地塊：
現在輪到七南進行劃分。他的任務是：將整塊農田劃分成數個不重疊的矩形區塊，每個矩形必須：
- 必須恰有包含一塊七誠指定的特殊地；
- 面積必須等於該特殊地所標示的數值。
以下是完成劃分的範例圖：
請你協助七南，繪製一種劃分方式，使得所有要求皆被滿足。
Input Format
第一行包含兩個正整數 $H, W$，代表農田的高度與寬度。
接下來有 $H$ 行，每行包含 $W$ 個整數 $a_{i,j}$，描述整張農田：
- 若 $a_{i,j} = 0$，表示該格為普通農地；
- 若 $a_{i,j} > 0$，表示該格為特殊地，該數值表示對應作物應分配的總面積。
資料範圍：
- $1 \leq H, W \leq 10$
- $0 \leq a_{i,j} \leq HW$
- $\sum\limits_{i=1}^ {H} \sum\limits_{j=1}^ {W} a_{i,j} = HW$
- 特殊地（$a_{i,j} > 0$）的數量不超過 $5$
- 保證輸入資料一定有解
Output Format
設特殊地總共有 $k$ 塊，你需要輸出一個 $H \times W$ 的矩陣。矩陣中每個格子填入一個介於 $1$ 到 $k$ 的整數，代表該格子屬於哪一種作物。
每一種作物對應一個不重疊的矩形區域，矩形中必須包含恰好一個對應的特殊地，且該區域的格子數量必須等於該特殊地的面積值。
若有多組解，請輸出任意一組即可。
Sample Input 1
5 5 5 0 6 0 0 0 0 0 0 5 0 3 6 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 1
1 2 2 2 3 1 2 2 2 3 1 4 5 5 3 1 4 5 5 3 1 4 5 5 3
Hints
Problem Source
YTP 2025 高中組程式挑戰營 p9
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測試資料 | 0 |
| 2 | 0~30 | 無額外限制 | 15 |