路徑: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不下棋。

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

注意

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

解法

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

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

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

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

語法

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

C#

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
        }
    }
}

下載

VS2010 C# 版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()