內容
ICE ( 人名) 的部落在A國的北邊，他們不滿天寒地凍的環境，於是準備向A國的南方征戰來獲得更大的領土。
A國的領土，我們用一個 m*n 的矩陣來描述，其中某些地方是城鎮，某些地方是高山無人居住。 ICE 把自己的部落分成幾支軍隊，他們約定：
- 每支軍隊可以從任意一個城鎮出發，並只能從上往向下征戰，不能回頭。途中只能經過城鎮，不能經過高山。
- 如果某個城鎮被某支軍隊到過，則其他軍隊不能再去那個城鎮了。
- 每支軍隊都可以在任意一個城鎮停止征戰。
- 所有軍隊都很奇怪，他們走的方法有點像象棋中的馬。不過馬每次只能走 1*2 的路線，而他們只能走 R*C 的路線。
ICE 的野心是要統一全國，但兵力的限制讓他們在配備人手時，感到力不從心。假設他們每支軍隊都能順利佔領這支軍隊經過的所有城鎮，請你幫 ICE 算算，至少要多少支軍隊才能完成統一全國的大業。
範例一
範例二
輸入說明
【輸入格式】
第一行包含4個整數 n、m、R、C，意義見問題描述。
接下來 n 行每行一個長度為 m 的字串。如果某個字元是 '.'，表示這個地方是城鎮。如果這個字元是 'x'，表示這個地方是高山。
輸出說明
【輸出格式】
輸出一個整數，表示最少的軍隊個數
範例輸入
#1
【範例輸入一】 3 3 1 2 ... .x. ... 【範例輸入二】 5 4 1 1 .... ..x. ...x .... x...
範例輸出
#1
【範例輸出一】 4 【範例輸出二】 5
測資資訊：
記憶體限制：
64
MB
提示 ：
【分數】
20% 1 <= m, n <= 4 and r = c = 1
40% 1 <= m, n <= 10 and 1 <= r, c <= 3
60% 1 <= m, n <= 20 and 1 <= r, c <= 3
80% 1 <= m, n <= 30 and 1 <= r, c <= 5
100% 1 <= m, n <= 50 and 1 <= r, c <= 10
標籤:
出處:
2018成功高中校內賽
[管理者：
bl33234679
(StillFantasy)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||