題目連結:
題目大意:
輸入第一列給定一正整數,代表有幾筆測試資料。測資第一列給定兩正整數 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)去找每個語言相同的區域即可(如
這題)。然後對每個語言按照題目的要求排序並輸出即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。