內容
西元 3000 年的總統選舉要到了，在連任了將近一千年後，豬哥會社黨提派的仍然是豬大哥。
可以把選區看成一個由 $n\times m$ 個格子組成的矩形，其中有些格子有住人，有些沒有，有住人的格子用 $1$ 表示，否則用 $0$ 表示。
要將 $n\times m$ 個格子劃分成若干個選舉區，因為選舉區劃分的越多，成本也會越高，所以選舉區越少越好，需要滿足：
- 每個有住人的格子恰屬於一個選舉區，沒住人的格子不屬於任何選舉區。
- 每個選舉區的形狀是一個實心的矩形，也就是所有在這個矩形範圍內的格子都屬於這個選舉區，並且都有住人。
請你回答最少要劃分幾個選舉區，並構造一組答案。
輸入說明
第一行輸入兩個正整數 $n, m$。
接下來 $n$ 行，每行輸入 $m$ 個整數，代表這一行的 $m$ 個格子分別有沒有住人。
- $1\leq n\leq 2000$
- $1\leq m\leq 8$
- 至少有一個格子有住人
輸出說明
輸出一個整數 $k$ 代表最少要劃分 $k$ 個選舉區。
接下來 $n$ 行，第 $i$ 行輸出 $m$ 個整數 $a_{i,1}\sim a_{i,m}$，滿足 $0\leq a_{i,j}\leq k$。
若 $a_{i,j}=0$，代表這個格子沒有住人；否則若 $a_{i,j}=x$（$1\leq x\leq k$），代表這個格子屬於第 $x$ 個選舉區。
可以自行對選舉區編號，只要滿足所有同編號且有住人的格子組成一個實心矩形就可以了。
範例輸入
#1
1 1 1
範例輸出
#1
1 1
範例輸入
#2
2 3 1 1 1 1 1 0
範例輸出
#2
2 1 1 2 1 1 0
範例輸入
#3
4 4 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1
範例輸出
#3
4 4 0 0 3 4 1 0 3 4 2 2 3 4 0 0 3
測資資訊：
記憶體限制：
256
MB
不公開 測資點#0 (2%): 2.5s , <1K
不公開 測資點#1 (2%): 2.5s , <1K
不公開 測資點#2 (2%): 2.5s , <1K
不公開 測資點#3 (2%): 2.5s , <1K
不公開 測資點#4 (3%): 2.5s , <1K
不公開 測資點#5 (3%): 2.5s , <1K
不公開 測資點#6 (3%): 2.5s , <1K
不公開 測資點#7 (3%): 2.5s , <1K
不公開 測資點#8 (10%): 2.5s , <1M
不公開 測資點#9 (10%): 2.5s , <1M
不公開 測資點#10 (10%): 2.5s , <1M
不公開 測資點#11 (10%): 2.5s , <1M
不公開 測資點#12 (10%): 2.5s , <1M
不公開 測資點#13 (10%): 2.5s , <1M
不公開 測資點#14 (10%): 2.5s , <1M
不公開 測資點#15 (10%): 2.5s , <1M
不公開 測資點#0 (2%): 2.5s , <1K
不公開 測資點#1 (2%): 2.5s , <1K
不公開 測資點#2 (2%): 2.5s , <1K
不公開 測資點#3 (2%): 2.5s , <1K
不公開 測資點#4 (3%): 2.5s , <1K
不公開 測資點#5 (3%): 2.5s , <1K
不公開 測資點#6 (3%): 2.5s , <1K
不公開 測資點#7 (3%): 2.5s , <1K
不公開 測資點#8 (10%): 2.5s , <1M
不公開 測資點#9 (10%): 2.5s , <1M
不公開 測資點#10 (10%): 2.5s , <1M
不公開 測資點#11 (10%): 2.5s , <1M
不公開 測資點#12 (10%): 2.5s , <1M
不公開 測資點#13 (10%): 2.5s , <1M
不公開 測資點#14 (10%): 2.5s , <1M
不公開 測資點#15 (10%): 2.5s , <1M
提示 ：
豬大哥勝選感言：「這是我人生當中，最刺激、最緊張。沒有人了解我的心裡，啊我們不要說打敗誰，是他們同情我啦。我那麼老了，人家還那麼喜歡看我，那我會拼命，做到大家高興這樣就好啦。」
---------------------------------------------------
$20\%：n,m\leq 4$
$80\%：無特別限制$
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||