c729: ICE 瘋狂炫技
標籤 :
通過比率 : 50% (1 人 / 2 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-11-27 14:35

內容

ICE ( 人名) 的部落在A國的北邊,他們不滿天寒地凍的環境,於是準備向A國的南方征戰來獲得更大的領土。

A國的領土,我們用一個 m*n 的矩陣來描述,其中某些地方是城鎮,某些地方是高山無人居住。 ICE 把自己的部落分成幾支軍隊,他們約定:

 

  1. 每支軍隊可以從任意一個城鎮出發,並只能從上往向下征戰,不能回頭。途中只能經過城鎮,不能經過高山。
  2. 如果某個城鎮被某支軍隊到過,則其他軍隊不能再去那個城鎮了。
  3. 每支軍隊都可以在任意一個城鎮停止征戰。
  4. 所有軍隊都很奇怪,他們走的方法有點像象棋中的馬。不過馬每次只能走 1*2 的路線,而他們只能走 R*C 的路線。

 

ICE 的野心是要統一全國,但兵力的限制讓他們在配備人手時,感到力不從心。假設他們每支軍隊都能順利佔領這支軍隊經過的所有城鎮,請你幫 ICE 算算,至少要多少支軍隊才能完成統一全國的大業。

 

範例一

範例二

 

輸入說明

【輸入格式】

第一行包含4個整數 n、m、R、C,意義見問題描述。

接下來 n 行每行一個長度為 m 的字串。如果某個字元是 '.',表示這個地方是城鎮。如果這個字元是 'x',表示這個地方是高山。

輸出說明

【輸出格式】

輸出一個整數,表示最少的軍隊個數

範例輸入
【範例輸入一】
3 3 1 2
...
.x.
...


【範例輸入二】
5 4 1 1
....
..x.
...x
....
x...

範例輸出
【範例輸出一】
4


【範例輸出二】
5
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (20%): 1.0s , <1K
不公開 測資點#3 (20%): 1.0s , <1K
不公開 測資點#4 (20%): 1.0s , <1M
提示 :

 

【分數】

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)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」