前往
大廳
主題

ZeroJudge - f822: 紅林愛下棋 解題心得

Not In My Back Yard | 2021-05-24 00:00:04 | 巴幣 0 | 人氣 235

題目連結:


題目大意:
輸入給定一個 9 列 9 行的字元陣列,代表一局圍棋的局面。黑方以「B」、白方以「W」、空地以「.」表示。

一塊空地(由多個相鄰空地組成)屬於黑方或是白方之條件為,其周遭只被黑色或是白色圍繞著。

當有空地同時被兩方圍繞著時,請輸出「Wrong」。反之,則請統計該局面哪方的佔地較大。根據佔地大小而輸出黑白方誰贏、輸出佔地比例(黑:白),並將所有屬於黑白方之佔地之「.」字元變成「B」或是「W」(以示是黑方或白方佔地)後輸出整個盤面。輸出格式請參見範例輸出。



範例輸入:
範例輸入 #1
.........
.B.....B.
BBB....BB
BBBBBBBBB
WWWWWWWWW
WWW..WWWW
WWWWWWWBB
.....WBB.
.....WB.B

範例輸入 #2
.........
.B.....B.
BBB....BB
BBBBBBBBB
WWWW.WWWW
WWW..WWWW
WWWWWWWBB
......WB.
......WBB


範例輸出:
範例輸出 #1
Black wins!!
44:37
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
WWWWWWWWW
WWWWWWWWW
WWWWWWWBB
WWWWWWBBB
WWWWWWBBB

範例輸出 #2
Wrong
//中間那塊被B和W圍著(此行不須輸出)


解題思維:
利用廣度優先搜尋(Breadth First Search,BFS)的精神走過每塊空地(如這題),而且在擴散的時候,看是否有擴散到「B」或是「W」,代表該地屬於黑方或是白方。如果這一塊空地同時擴張到「B」和「W」,則代表這塊兩方同時佔有,因此輸出「Wrong」。

邊擴散邊統計兩方的佔地大小,並且將分別屬於兩者的空地之字元改為「B」或是「W」(看要是擴張的時候就改,還是先記錄最後輸出的時候在更改)。

最後根據佔地大小輸出誰贏、比數以及最終盤面即可。




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

創作回應

更多創作