《算法竞赛入门经典》习题4-3 黑白棋（Othello, ACM、ICPC World Finals 1992, UVa220）
原題及翻譯
Othello is a game played by two people on an 8 x 8 board, using disks that are white on one side and black on the other.
奧賽羅是一個由兩個人在一個8×8的棋盤上玩的游戲，使用的是一面是白色，另一面是黑色的棋子。
One player places disks with the white side up and the other player places disks with the black side up.
一位玩家將棋子放在白色朝上的位置，另一位玩家將棋子放在黑面朝上的位置。
The players alternate placing one disk on an unoccupied space on the board.
玩家交替地將棋子放在游戲板上一個未占用的空間上。
In placing a disk, the player must bracket at least one of the other color disks.
在放置棋子時，玩家必須將另一個顏色的棋子中的至少一個放入棋盤。
Disks are bracketed if they are in a straight line horizontally, vertically, or diagonally, with a disk of the current player’s color at each end of the line.
如果棋子在水平、垂直或對角的直線上，則棋子加括號，并且在該直線的兩端各有一個當前玩家顏色的棋子。
When a move is made, all the disks that were bracketed are changed to the color of the player making the move.
移動時，括號內的所有棋子都將更改為進行移動的玩家的顏色。
(It is possible that disks will be bracketed across more than one line in a single move.)
（棋子可能會在一次移動中跨多行被括號括住。）
On the left
在左邊
Legal Moves for White
白色的合法移動
(2,3),(3,3),(3,5),(3,6)(6,2),(7,3),(7,4),(7,5)
On the right
在右邊
Board Configuration after White Moves to (7,3)
白板棋子移到（7,3）
Write a program to read a series of Othello games.
編寫一個程序來閱讀一系列奧賽羅游戲。
Input
輸入
The first line of the input is the number of games to be processed.
輸入的第一行是要處理的游戲數。
Each game consists of a board configuration followed by a list of commands.
每個游戲由一個游戲板和一個命令列表組成。
The board configuration consists of 9 lines.
游戲板由9條線路組成。
The first 8 specify the current state of the board.
前8個指定板的當前狀態。
Each of these 8 lines contains 8 characters, and each of these characters will be one of the following:
這8行中的每一行包含8個字符，每個字符都是以下字符之一：
‘-’ indicating an unoccupied square
“-”表示一個空位
‘B’ indicating a square occupied by a black disk
“B”表示黑色棋子所占的正方形
‘W’ indicating a square occupied by a white disk
“W”表示白色棋子所占的正方形
The ninth line is either a ‘B’ or a ‘W’ to indicate which is the current player.
第九行是“B”或“W”，表示當前玩家。
You may assume that the data is legally formatted.
您可以假定數據是合法格式化的。
Then a set of commands follows.
接下來是一組命令。
The commands are to list all possible moves for the current player, make a move, or quit the current game.
命令是列出當前玩家的所有可能移動或退出當前游戲。
There is one command per line with no blanks in the input
每行有一個命令，輸入中沒有空格。
Output
輸出
The commands and the corresponding outputs are formatted as follows:
命令和相應輸出的格式如下：
List all possible moves for the current player.
列出當前玩家的所有可能移動。
The command is an ‘L’ in the first column of the line.
命令是L行的第一列。
The program should go through the board and print all legal moves for the current player in the format (x, y) where x represents the row of the legal move and y represents its column.
程序應該瀏覽棋盤并以格式（x，y）打印當前玩家的所有合法移動，其中x代表合法移動的行，y代表其列。
These moves should be printed in row major order which means:
這些移動應按行主要順序打印，這意味著：
1)all legal moves in row number i will be printed before any legal move in row number j if j is greater than i
1）行號i中的所有合法移動將在行號j中的任何合法移動之前打印，如果j大于i
2) if there is more than one legal move in row number i, the moves will be printed in ascending order based on column number.
2）如果第i行中有多個合法移動，移動將根據列號按升序打印。所有合法的行動都應該放在同一條線上。
All legal moves should be put on one line. If there is no legal move because it is impossible for the current player to bracket any pieces, the program should print the message ‘No legal move.’
如果由于當前玩家無法將任何棋子放在括號內而沒有合法移動，程序應打印消息“無合法移動”。
Make a move.
行動起來。
The command is an ‘M’ in the first column of the line, followed by 2 digits in the second and third column of the line.
命令是行的第一列中的“m”，然后是行的第二列和第三列中的2位數字。
The digits are the row and the column of the space to place the piece of the current player’s color, unless the current player has no legal move.
除非當前玩家沒有合法移動，否則數字是放置當前玩家顏色塊的空間的行和列。
If the current player has no legal move, the current player is first changed to the other player and the move will be the move of the new current player.
如果當前玩家沒有合法移動，則當前玩家首先被更改為其他玩家，移動將是新的當前玩家的移動。
You may assume that the move is then legal.
你可以假設這是合法的。
You should record the changes to the board, including adding the new piece and changing the color of all bracketed pieces.
您應該記錄對游戲板的更改，包括添加新棋子和更改所有帶括號的棋子的顏色。
At the end of the move, print the number of pieces of each color on the board in the format ‘Black - xx White - yy’ where xx is the number of black pieces on the board and yy is the number of white pieces on the board.
在移動結束時，以“黑色-XX白色-YY”格式打印板上每種顏色的棋子數，其中XX是板上的黑色棋子數，YY是板上的白色棋子數。
After a move, the current player will be changed to the player that did not move.
移動后，當前玩家將更改為未移動的玩家。
Quit the current game.
退出當前游戲。
The command will be a ‘Q’ in the first column of the line.
命令將是行的第一列中的“q”。
At this point, print the final board configuration using the same format as was used in the input.
此時，使用輸入中使用的相同格式打印最終游戲板。
This terminates input for the current game.
這將終止當前游戲的輸入。
You may assume that the commands will be syntactically correct.
您可以假定這些命令在語法上是正確的。
Put one blank line between output from separate games and no blank lines anywhere else in the output.
在不同游戲的輸出之間放置一個空白行，而輸出中的其他任何地方都沒有空白行。
Sample Input
樣例輸入
Sample Output
樣例輸出
分析
1.做這道題最關鍵的是要讀懂題，一開始看純英文原題的時候，看到兩張黑白棋圖，想當然的就以為是五子棋，然后以五子棋的規則去讀題，結果完全稀里糊涂的，然后用百度翻譯去翻譯，（百度翻譯一翻譯長文章就不行了，disk翻譯成磁盤，其實應該翻譯成棋子，player翻譯成播放器，其實應該是玩家）。
2.要知道奧賽羅的規則：黑白雙方輪流放棋子，每次必須讓新放的棋子“夾住”至少一枚對方棋子，然后把所有被新放棋子“夾住”的對方棋子替換成己方棋子。一段連續（橫、豎或者斜向）的同色棋子被“夾住”的條件是兩端都是對方棋子（不能是空位）。
思路
1.首先，由于還是棋盤游戲類問題，需要一個二維數組來儲存棋盤的所有結點信息（Checkerboard[8][8]），一個含有兩個元素的數組來存儲黑棋和白棋的個數（Number_of_pieces[2]），由于輸入的命令可能是L和Q單個字母，也可能是M35這種字母數字組合型，所以要聲明一個char類型的數組來存儲命令command[8]，還有兩個數組（Runx[8]，Runy[8]），如果只看這兩個數組的話可能不知道什么意思，但是不得不說，能想出來這種方法的人真實牛牪犇，因為這兩個數組我又把我原來的代碼重新改了一遍。由于這些變量要在整個程序中使用，所以聲明為全局變量。
#include <stdio.h> #include <string.h> char Checkerboard[8][8]; char Current_piece,command[8]; int Number_of_pieces[2]={0,0}; int Runx[8]={0,0,1,-1,1,-1,1,-1}; int Runy[8]={1,-1,0,0,1,-1,-1,1}; bool Flag, L_Refresh;2.其次，分析題目需要什么重復使用的功能，把這些功能寫成函數能減少很多思考量。
a、因為判斷當前玩家是否有合法操作之后要決定是否換成下一位玩家，所以先寫一個簡單的交換函數。
b、題目中有要求打印出黑白棋子的個數，這可以作為一個單獨的代碼塊：
for (int i = 0; i < 8; ++i){//統計黑白棋的個數for (int j = 0; j < 8; ++j){if (Checkerboard[i][j] == 'W') Number_of_pieces[0]++;else if (Checkerboard[i][j] == 'B') Number_of_pieces[1]++;}}c、Q命令要求退出游戲并打印整個游戲板，這個比較簡單，可以寫一個簡單的函數：
void Q() {//打印整個游戲板for(int i=0;i<8;i++){for(int j=0;j<8;j++){printf("%c",Checkerboard[i][j]);}printf("\n");} }接下來就要寫一些比較復雜的函數了，比如L命令和M命令，還有判斷棋子是否合法以及翻轉棋子的函數。
d、先來寫主函數確定整體框架，主函數包括讀入數據和對數據做處理，還有調用各種函數：
int main() {int n;scanf("%d",&n);//讀入游戲的次數while (n--){for (int i = 0; i < 8; ++i) scanf("%s", Checkerboard[i]);//直接將一行的字符串讀入到游戲板上scanf("\n%c", &Current_piece);//讀入當前選手的棋子類型L_Refresh = 0;Number_of_pieces[0] = Number_of_pieces[1] = 0;for (int i = 0; i < 8; ++i){//統計黑白棋的個數for (int j = 0; j < 8; ++j){if (Checkerboard[i][j] == 'W') Number_of_pieces[0]++;else if (Checkerboard[i][j] == 'B') Number_of_pieces[1]++;}}while(scanf("%s",command)){if(command[0]=='L') L(true);else if(command[0]=='M') M();else if(command[0]=='Q'){Q();break;}}if (n) printf("\n");}return 0; }e、然后是L函數，L函數要打印所有的合法操作，這就需要一個判斷棋子是否合法的函數了：
L（）：
這里就用到了我前邊說的那個很神奇的想法，利用數組遍歷i，j周圍的八個 位置，比用八個if判斷有省力很多（我之前就這么干過，很費勁）。
judge（）：
judge函數在M命令的時候同樣也要用到，所以先寫出來。
f、最后是M函數，因為M命令中有需要翻轉棋子的內容，所以還要寫一個翻轉棋子的函數，注意翻轉后要重新統計黑白棋子的個數。
M（）：
change（）：
void change(int i, int j, int x, int y) {//將能翻轉的棋子翻轉并統計黑白棋個數int n = 0;while (Checkerboard[i+=x][j+=y]!=Current_piece){Checkerboard[i][j]=Current_piece;n++;//將棋子翻轉然后統計翻轉棋子的個數}//判斷棋子的類型然后累加黑白棋的個數if(Current_piece=='W'){Number_of_pieces[0]+=n;Number_of_pieces[1]-=n;}if(Current_piece=='B'){Number_of_pieces[0]-=n;Number_of_pieces[1]+=n;} }完整代碼
#include <stdio.h> #include <string.h> char Checkerboard[8][8]; char Current_piece,command[8]; int Number_of_pieces[2]={0,0}; int Runx[8]={0,0,1,-1,1,-1,1,-1}; int Runy[8]={1,-1,0,0,1,-1,-1,1}; bool Flag, L_Refresh; void Exchange_player() {//用于交換當前玩家。if(Current_piece=='W') Current_piece='B';if(Current_piece=='B') Current_piece='W'; } bool judge(int i, int j, int x, int y, bool Whether) {//判斷函數int a=i+1,b=j+1,flag=0;while((i+=x)<8&&(j+=y)<8&&i>=0&&j>=0){//保證不越界的情況下if (Checkerboard[i][j] == '-') break;//如果當前位置沒有棋子，則直接退出if (Checkerboard[i][j] ==Current_piece){//在i，j位置放下當前玩家的棋子if (!flag) break;//當flg不為0的時候，退出if (Whether){if (Flag) printf(" ");printf("(%d,%d)",a,b);}if (!Flag)Flag=true;return true;}flag++;}return false; } void change(int i, int j, int x, int y) {//將能翻轉的棋子翻轉并統計黑白棋個數int n = 0;while (Checkerboard[i+=x][j+=y]!=Current_piece){Checkerboard[i][j]=Current_piece;n++;//將棋子翻轉然后統計翻轉棋子的個數}//判斷棋子的類型然后累加黑白棋的個數if(Current_piece=='W'){Number_of_pieces[0]+=n;Number_of_pieces[1]-=n;}if(Current_piece=='B'){Number_of_pieces[0]-=n;Number_of_pieces[1]+=n;} } void L(bool Whether) {//打印所有的合法操作，按照從上到下，從左到右的順序L_Refresh=1;Flag=0;for (int i=0;i<8;i++){//遍歷棋盤的所有位置for (int j=0;j<8;j++){if (Checkerboard[i][j] != '-') continue;//跳過所有i，j位置上有棋子的點for (int x=0;x<8;x++){//遍歷i，j位置周圍八個點if (judge(i,j,Runx[x],Runy[x],Whether)) break;}}}if (Whether)Flag?printf("\n"):printf("No legal move.\n"); } void M() {char i=command[1]-49,j=command[2]-49;//將行和列轉換成數字需要減去‘0’字符對應的序號if (!L_Refresh) L(0);if (!Flag) Exchange_player();for (int x=0;x<8;x++){//八次循環將i，j位置周圍八個棋子全部遍歷并判斷能否改變if (judge(i,j,Runx[x],Runy[x],0)) change(i,j,Runx[x],Runy[x]);}Current_piece=='W'?Number_of_pieces[0]+=1:Number_of_pieces[1]+=1;//累加黑白棋子的個數Checkerboard[i][j] =Current_piece;Exchange_player();//改變玩家L_Refresh = 0;printf("Black - %2d White - %2d\n", Number_of_pieces[1], Number_of_pieces[0]);//打印黑白棋子的數目 } void Q() {//打印整個游戲板for(int i=0;i<8;i++){for(int j=0;j<8;j++){printf("%c",Checkerboard[i][j]);}printf("\n");} } int main() {int n;scanf("%d",&n);//讀入游戲的次數while (n--){for (int i = 0; i < 8; ++i) scanf("%s", Checkerboard[i]);//直接將一行的字符串讀入到游戲板上scanf("\n%c", &Current_piece);//讀入當前選手的棋子類型L_Refresh = 0;Number_of_pieces[0] = Number_of_pieces[1] = 0;for (int i = 0; i < 8; ++i){//統計黑白棋的個數for (int j = 0; j < 8; ++j){if (Checkerboard[i][j] == 'W') Number_of_pieces[0]++;else if (Checkerboard[i][j] == 'B') Number_of_pieces[1]++;}}while(scanf("%s",command)){if(command[0]=='L') L(true);else if(command[0]=='M') M();else if(command[0]=='Q'){Q();break;}}if (n) printf("\n");//換行}return 0; }結語
“努力不一定有收獲，但是不努力一定沒有收獲！”
每天磕一道ACM 除夕打卡
總結
以上是生活随笔為你收集整理的《算法竞赛入门经典》习题4-3 黑白棋（Othello, ACM、ICPC World Finals 1992, UVa220）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《算法竞赛入门经典》习题4-2 正方形
- 下一篇： 《算法竞赛入门经典》 例题 4-4 信息