f835: 進擊的DD
Tags : BFS DD DFS
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-16 18:30

Content

DD人物介紹 : https://zerojudge.tw/ShowProblem?problemid=f754

那一天,DD想起了被頭皮屑支配的恐懼。

阿卡D一族是DD王族的貼身護衛世家,負責保衛王世的安危,而阿卡D一族的能力是擁有彪悍超常的戰鬥力,但在獲得這個能力前必須先覺醒,舉個例子,紅林因為對圍棋念念不忘,想要拯救圍棋而成為圍棋師傅(可見題號 : f822 ) ,進而覺醒,可惜只有少少人去學習(還不去解ㄇ)。而今天巨人打破了DD之牆,DD王國的子民死傷慘重,顛沛流離,DD體內留著阿卡D的血液,從小他就被洗腦只要看到巨人格殺毋論,否則會像吃了香菜一樣難受,今天他的機會到了,身為國王的奴隸(對你沒看錯,他不是國王)的他想要拯救世界,懷著滿身的怨氣,滿身的頭皮屑,滿身的臭味。

他覺醒了!!!

DD的能力是巨人化,這表示DD可以在每筆測資發動一次D鳴,D鳴的作用是DD能用全身的頭皮屑召喚分身當跳板,也就是說可以放DD在地圖的任意一個地方(等同於巨人),但它的代價是輸出時要輸出"DD好醜"(不含引號),對DD而言,這是個莫大的恥辱,甚至寧願吃香菜也不要發動(DD你不洗頭卻在意顏值???)。

請寫出一個程式,算出DD所以地圖加起來最少需要幾刀才能讓萊納(巨人)坐下。以DD的技術,他每刀的範圍可以砍以巨人為中心的3*3範圍。

//砍死的巨人的3*3範圍也會是DD每刀的範圍

//這項技能不一定要使用,但如果用了每筆測資只能用次,請運用在最好的情況。

 

 

 
Input

第一行有兩個整數 T,G,T代表有幾筆測資,G代表每筆測資有幾張地圖。

接著有G張地圖 ( d代表空地, D代表巨人)。

每張地圖的第一行為 M , N 兩數 ,代表地圖大小。 1<M,N<3000000。

接著有M*N大小的地圖。

 

 

Output

算出DD所有地圖加起來最少需要幾刀才能讓萊納(巨人)坐下。

若發動D鳴要輸出"DD好醜"(不含引號)。

 

Sample Input #1
1 1
3 6
dddddd
dDdDDd
ddDddD
Sample Output #1
1
Sample Input #2
1 2 
4 6
Dddddd
ddDddd
dDdDdd
dddddD

5 5
DdDdd
dDddd
DDdDd
ddddD
DDddd
Sample Output #2
4 DD好醜 // D鳴用在第二張地圖座標(3,4)
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (50%): 0.5s , <1K
不公開 測資點#1 (50%): 1.0s , <1K
Hint :

真D難

Tags:
BFS DD DFS
出處:
DD的奇幻冒險之旅 [管理者:
_xdddd ((找不到本用戶!))
]


ID User Problem Subject Hit Post Date
25318
yes51851823@... (wseds)
f835
別被範圍嚇到
140 2021-05-11 11:35