前往
大廳
主題

ZeroJudge - d365: 10336 - Rank the Languages 解題心得

Not In My Back Yard | 2021-06-29 00:00:06 | 巴幣 0 | 人氣 216

題目連結:


題目大意:
輸入第一列給定一正整數,代表有幾筆測試資料。測資第一列給定兩正整數 H 、 W,代表有 H × W 個地圖,每格網格代表一個地區所講的語言(語言以小寫字母 'a' ~ 'z' 表示)。接著有 H 列輸入,每列給定 W 個字元,代表地圖每地區的語言。

一個區域為複數的地區上下左右相鄰地連接在一起。試問對於每種語言有幾個區域說該種語言。請將語言區域數按照大到小排序並輸出,區域數一樣則按照語言字典序排序。輸出格式參見範例輸出。



範例輸入:
2
4 8
ttuuttdd
ttuuttdd
uuttuudd
uuttuudd
9 9全
bbbbbbbbb
aaaaaaaab
bbbbbbbab
baaaaacab
bacccccab
bacbbbcab
bacccccab
baaaaaaab
bbbbbbbbb


範例輸出:
World #1
t: 3
u: 3
d: 1
World #2
b: 2
a: 1
c: 1


解題思維:
套用廣度優先搜尋(Breadth First Search,BFS)去找每個語言相同的區域即可(如這題)。然後對每個語言按照題目的要求排序並輸出即可。




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

創作回應

更多創作