切換
舊版
前往
大廳
主題

ZeroJudge - a597: 祖靈被榨乾了!!!!!!!! 解題心得

Not In My Back Yard | 2019-05-29 23:08:21 | 巴幣 0 | 人氣 529

題目連結:


題目大意:
題目包含多組測試資料,每組測試資料第一列給定兩正整數 m 、 n (0 < m 、 n ≦ 500),代表接下來有 m 列輸入,每列有 n 個字元。

每個字元只會是「X」或是「J」,「J」代表有所謂的「JIZZ」在這格地板上;反之,「X」則代表這格地板是正常的地板。

一「灘」JIZZ 定義為,在這灘 JIZZ 裡,每個「J」都在彼此的上下左右。例如:
JJJ
JXX
當中只有一灘 JIZZ ,而
JX
XJ
中有兩灘的 JIZZ 。

現在給定這 m × n 的地板,求地板上有幾灘 JIZZ ,以及最大的那灘 JIZZ 佔了多少格地板。



範例輸入:
5 5
XXXXX
XXJJX
XJJJX
XXXXX
XJXXX


範例輸出:
2 5


解題思維:
典型的廣度優先搜尋(BFS)題型。

首先,先把題目給定的 m × n 大小的地板讀進來並存入一二維陣列裡。不過因為資料量很大,C++ 的話建議使用 scanf、printf 輸出入;不然,至少也要最佳化一下輸出入

接著就掃過每個地板,當遇到「J」的時候便開始執行廣度優先搜尋:
先把這個地板的位置資訊丟進佇列(Queue)裡,並將此格設為「已探訪過」。

當佇列不為空時,把佇列最前面的元素拿出,也就是會得到某個地板的位置。判斷該塊地板的上下左右的地板。如果有為「J」的地板,就加到佇列的尾端,同時將該格也設為「已探訪過」。如果遇到「已探訪過」的「J」地板,則不加入佇列裡。

重複以上步驟直到佇列為空。而佇列被加入過多少元素,即為此灘 JIZZ 所佔的地板數。

佇列為空之後,就可以繼續上面掃描地板的迴圈,看是否有下一灘 JIZZ 。而當遇到「已探訪過」的「J」地板時,則代表該格「J」屬於前面已經找到的某灘 JIZZ 。故應略過。



結束掃描的過程之後,即可知道總共有幾灘 JIZZ (進入 BFS 的程序多少次)。而稍微紀錄一下,也就可以知道最大灘的 JIZZ 佔了多少地板。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作