切換
舊版
前往
大廳
主題

ZeroJudge - e173: 圍棋入門 - 真眼假眼 解題心得

Not In My Back Yard | 2019-05-07 21:30:24 | 巴幣 0 | 人氣 195

題目連結:


題目大意:
給定一正整數 n (5 ≦ n ≦ 19, n = 0 時停止程式),代表有一 n × n 的棋盤。

接著有 n 列輸入,每列有 n 個字元。「O」代表黑棋,「X」代表白棋,「.」代表沒有任何棋子。而這個棋盤的左下角座標為(1, 1),右上角為(n, n)。

接著給定一正整數 q (1 ≦ q ≦ 100),代表接下來有 q 列輸入。每列輸入給定兩正整數 x 、 y (1 ≦ x 、 y ≦ n),試問棋盤上(x, y)的位置是否為真眼或是假眼。若為真眼,輸出「Real!」;若為假眼,輸出「Fake!」;若以上皆非,輸出「Interesting...」。

而「眼」的定義為,一個位置的上下左右都是被同一方棋子所佔(若是邊邊角角的位置,則只需考慮棋盤內的地方)。而「真眼」是對角線的位置也至少有三個同方的棋子所佔,而邊緣以及角落的位置則分別需要周圍 5 格、 3 格為同方才算真眼;「假眼」則是不符合真眼定義的眼位。



範例輸入:
5
XX...
X.X..
XXXO.
OOO.O
.O.O.
4
1 1
4 2
2 4
5 5
0


範例輸出:
Real!
Fake!
Real!
Interesting...


解題思維:
先分別計算給定的座標之相鄰(上下左右)以及對角(左上、右上、左下、右下)的黑棋、白棋數。再判斷(x, y)這個位置是角落、邊緣還是一般的棋位。

若(x, y)在角落,則同一方(白方、黑方)相鄰為兩個棋子即為「眼」,而若對角也有一個同方棋子即是「真眼」;若對角沒有棋子或是是另一方的棋子,則是「假眼」。

若(x, y)在邊緣,則類似上面的情況,同一方佔有相鄰位置三個(也只有三個可以佔就是了)為「眼」,對角有兩個同方的即為「真眼」;對角同方兩個以下(不含)的為「假眼」。

若(x, y)在內部,同一方佔有相鄰的所有位置為「眼」,對角要佔三個以上才算「真眼」;三個以下(不含)算「假眼」。

而其他沒有提及的情況則全部視為非眼位。

除了注意輸入時,棋盤是由第 n 列到第 1 列由上至下給定以外,其他只要照著題目的規則判斷即可。

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

創作回應

胖胖貓
實際應該要用 DFS() 遞迴判斷,斜對角的空地是不是剛好也是眼位
只是這樣程式會變得極其複雜就是
2019-05-08 00:14:35
Not In My Back Yard
感謝大大的補充。
2019-05-08 11:43:23

相關創作

更多創作