TopCoder Inv 2001 Semi A+B - Tothello

資訊

路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ Tothello
分數：500

題目

程式介面

Class Name: Tothello
Method Name: bestMove
Parameters: String[], String[], String
Returns: int
Method signature (be sure your method is public):  int bestMove(String[] redPieces, String[] blackPieces, String whoseTurn);

說明

Tothello 是一個 Othello 遊戲的修改版，Othello 是一種兩人玩的遊戲，一方使用紅色的棋子，一方使用黑色的棋子，輪流在一個 8x8 大小的棋盤上下棋。當一方下棋之後，如果有將對方的棋子兩端包夾起來，對方的棋子就會變成自己的棋子；而若有棋子變成自己的棋子後，又產生其他的包夾，則又可以變成自己的棋子，直到沒有任何包夾。另外自己的回合的時候，也可以選擇 Pass 不下棋。

現在請實作一個程式，能夠找到最好的下法，能夠獲得最多棋子的結果。

注意

redPieces 是一個 String[] 表示紅色棋子目前在棋盤上的位置。
blackPieces 是一個 String[] 表示黑色棋子目前在棋盤上的位置。
使用大寫字母 A - H 和數字 1 - 8 來表示棋盤上的位置，A1 是最左上角，H8 是最右下角。
紅棋和黑棋數量不會相等，因為可能被吃或者 Pass。
包夾可以是垂直、水平或其他對角線上的格子，但不能有空格。例如：

- - - R - - - -
- - - B - - - -
- - - B - - - -   紅色包夾黑色，黑色將變成紅色
- - - B - - - -
- - - R - - - -


- - - R - - - -
- - - B B - - -
- - - B - B - -   紅色包夾黑色，黑色將變成紅色
- - - R R R R R


- - - R - - - -
- - - B R - - -
- - - - - - - -   沒有產生包夾
- - - R R - - -


R R R R R R R R
R - - - - - - R
R - B B - B - R
R - B B B B - R   沒有產生包夾
R - - - - - - R
R R R R R R R R

系統保證輸入

redPieces 和 blackPieces 陣列：長度範圍為 0-50。
陣列元素格式：大寫 A - H 和數字 1 - 8 組成，[A-H][1-8]。
whoseTurn：Red 或 Black。
輸入的棋盤不會有包夾的情況。
輸入的位址不會重複。
棋盤至少會有一個空格。

範例

輸入：
redPieces = [C2,C3,C4,C5,D4,E4,F2,F3,F4,F5,G6]
blackPieces = [B1,E1,G1,C6,H7,G4]
whoseTurn = "Black"
輸出：16
註：
棋盤狀態如下

  A B C D E F G H
1 - B - - B - B -
2 - - R - - R - -
3 - - R - - R - -
4 - - R R R R B -
5 - - R - - R - -
6 - - B - - - R -
7 - - - - - - - B
8 - - - - - - - -

走 C1 最好

  A B C D E F G H       A B C D E F G H       A B C D E F G H       A B C D E F G H
1 - B - - B - B -     1 - B B - B - B -     1 - B B - B - B -     1 - B B - B - B -
2 - - R - - R - -     2 - - B - - R - -     2 - - B - - R - -     2 - - B - - R - -
3 - - R - - R - -     3 - - B - - R - -     3 - - B - - R - -     3 - - B - - R - -
4 - - R R R R B - --> 4 - - B R R R B - --> 4 - - B B B B B - --> 4 - - B B B B B -
5 - - R - - R - -     5 - - B - - R - -     5 - - B - - R - -     5 - - B - - B - -
6 - - B - - - R -     6 - - B - - - R -     6 - - B - - - R -     6 - - B - - - B -
7 - - - - - - - B     7 - - - - - - - B     7 - - - - - - - B     7 - - - - - - - B
8 - - - - - - - -     8 - - - - - - - -     8 - - - - - - - -     8 - - - - - - - -

最後共有 16 個棋子。

輸入：
redPieces=[A1,B8,C6,C8,D8]
blackPieces=[B2,C2,C3,C4,C5]
whoseTurn="Red"
輸出：11
註：走 C1 最好，最後有 11 個棋子。

解法

看完題目描述後會發現其實是黑白棋的遊戲，只是規則有些不同，其中多了一種可以不下的選擇。而不下的選擇在這個題目裡面只是用來符合某些情況的邏輯，讓輸入的資料可以有更多彈性，實際上在實作程式時倒是不用考慮。

在這題目中比較需要注意的是，棋盤上的包夾可能會再引起其他包夾，對於這樣的特性我們可以很簡單的使用遞迴來達成。我利用直覺的思考方式設計以下步驟：

找出可以下的地方，然後模擬下了之後會增加多少棋子，並找出最大值。
下了一個位置後，往八個方位去找可以增加多少棋子，總和起來。
每個方位先測試是否有包夾，有的話將包夾的棋子回到第2步遞迴，最後總和起來。

而在實作上需要注意的一點是，我們會去修改棋盤的狀態來模擬每個可能的結果，因此在每個模擬之後應該要有還原動作或者是用複本的方式來模擬，才不會影響到其他的模擬，而我這邊使用複本的方式。另外在進行遞迴前需先將棋盤的狀態更新完成，以免有路徑重複遞迴。

語法

採用較易理解的寫法，效能並非最好

using System;
using System.Collections.Generic;
using System.Text;

namespace Tothello
{
    class Tothello
    {
        private Piece[,] board;
        public int bestMove(string[] redPieces, string[] blackPieces, string whoseTurn)
        {
            board = new Piece[8, 8];
            foreach (string p in redPieces)
                board[p[1] - '1', p[0] - 'A'] = Piece.Red;
            foreach (string p in blackPieces)
                board[p[1] - '1', p[0] - 'A'] = Piece.Black;

            Piece piece = whoseTurn == "Red" ? Piece.Red : Piece.Black;
            int originalCount = whoseTurn == "Red" ? redPieces.Length : blackPieces.Length;
            int max = 0;
            for (int row = 0; row < 8; ++row)
                for (int col = 0; col < 8; ++col)
                    max = Math.Max(max, GetScore((Piece[,])board.Clone(), piece, row, col));

            return max + originalCount;
        }

        private int GetScore(Piece[,] board, Piece piece, int row, int col)
        {
            if (board[row, col] != Piece.None)
                return 0;
            board[row, col] = piece;
            return Trace(board, piece, row, col) + 1;
        }

        private int Trace(Piece[,] board, Piece piece, int row, int col)
        {
            int count = 0;
            count += Trace(board, piece, row, col, 0, 1);
            count += Trace(board, piece, row, col, 1, 0);
            count += Trace(board, piece, row, col, 1, 1);
            count += Trace(board, piece, row, col, 0, -1);
            count += Trace(board, piece, row, col, -1, 0);
            count += Trace(board, piece, row, col, -1, -1);
            count += Trace(board, piece, row, col, -1, 1);
            count += Trace(board, piece, row, col, 1, -1);
            return count;
        }

        private int Trace(Piece[,] board, Piece piece, int row, int col, int offsetRow, int offsetCol)
        {
            Piece opponent = piece == Piece.Black ? Piece.Red : Piece.Black;
            bool isBetween = false;
            List<KeyValuePair<int, int>> list = new List<KeyValuePair<int, int>>();
            for (int r = row + offsetRow, c = col + offsetCol; r < 8 && c < 8 && r >= 0 && c >= 0; r += offsetRow, c += offsetCol)
            {
                if (board[r, c] == piece)
                {
                    isBetween = true;
                    break;
                }
                else if (board[r, c] == opponent)
                    list.Add(new KeyValuePair<int, int>(r, c));
                else if (board[r, c] == Piece.None)
                    break;
            }
            if (!isBetween)
                return 0;

            int count = list.Count;
            foreach (KeyValuePair<int, int> pair in list)
                board[pair.Key, pair.Value] = piece;
            foreach (KeyValuePair<int, int> pair in list)
                count += Trace(board, piece, pair.Key, pair.Value);
            return count;
        }

        enum Piece
        {
            None,
            Red,
            Black
        }
    }
}