路徑:Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ ChessCover

分數:1000

題目

說明

在西洋棋中要避免你的King被攻擊,現在撰寫一套程式,系統輸入棋盤目前狀態,程式要從棋盤上找出安全的位置並回傳有多少個。棋盤上會出現以下五種棋子:

  1. Queen:可以攻擊八方位直線。
  2. Rook:可以攻擊上下左右直線。
  3. Bishop:可以攻擊斜角四方位直線。
  4. Knight:可以攻擊L位置(類似象棋馬的日字形)。
  5. Pawn:可以攻擊斜角四方位一格。

如下圖所示:

    Queen           Rook         Bishop         Knight          Pawn 
X + + X + + X  + + + X + + +  X + + + + + X  + + + + + + +  + + + + + + +
+ X + X + X +  + + + X + + +  + X + + + X +  + + X + X + +  + + + + + + +
+ + X X X + +  + + + X + + +  + + X + X + +  + X + + + X +  + + X + X + +
X X X Q X X X  X X X R X X X  + + + B + + +  + + + K + + +  + + + P + + +
+ + X X X + +  + + + X + + +  + + X + X + +  + X + + + X +  + + X + X + +
+ X + X + X +  + + + X + + +  + X + + + X +  + + X + X + +  + + + + + + +
X + + X + + X  + + + X + + +  X + + + + + X  + + + + + + +  + + + + + + +

輸入字串陣列表示棋盤的狀態,包含以下字元:

  1. U:表示沒有棋子。
  2. Q:表示Queen。
  3. R:表示Rook。
  4. B:表示Bishop。
  5. K:表示Knight。
  6. P:表示Pawn。

注意

  1. 你的King不再棋盤上,你的目的是算出有多少安全的位置。
  2. 棋盤可能全放滿棋子。
  3. 總共有五種棋子:Queen、Rook、Bishop、Knigh和Pawn。
  4. 相同的棋子可以一直重複放。
  5. 有棋子的位置不算安全的。
  6. 棋子可能會擋住別的棋子的攻擊路線。
  7. Knight不會被擋住。
  8. Pawn的攻擊和西洋棋規則不同。
  9. 棋盤不一定是正方形。

程式介面

Class name: ChessCover
Method name: getSafe
Parameters:  String[]
Returns: int
Method signature (be sure your method is public):  int getSafe (String[] boardLayout);

系統保證輸入

  • boardLayout的每一列元素長度為1-10。
  • boardLayout的每一列元素長度相等。
  • boardLayout的元素為以下字元[UQRBKP]。
  • boardLayout的列數長度為1-10。

範例

輸入:
UU
UU
輸出:4 輸入:
UUUUU
UQUQU
UUUUU 輸出:0 輸入:
UUU
UPU
UUU 輸出:4 輸入:
UUUU
UUUU
QUUU
UUUU
輸出:6
註:

X + X +
X X + +
Q X X X
X X + + 輸入:
UUUUUQ
UUUUUU
BURUUU
UUKUUU
UUUUUU
輸出:6
註:
X X X X X Q
+ X X X X X
B X R X X X
+ X K + + X
X + X + X X 輸入:
UBUKUUUBUU
UUUUBUUQUR 輸出:4
註:
+ B + K + X X B X X
X X X + B X X Q X R

解法

這一題我使用直覺的方式來實作,利用陣列表示棋盤的狀態,並將棋子放置後修改棋盤狀態,最後計算安全的位置。流程上有一點需要特別注意的是,棋子會擋住其他棋子的攻擊路線,所以應該要把棋子全部放上去之後在更新狀態。所以流程如下:

  1. 先將所有棋子放置到棋盤上。
  2. 將每個棋子的攻擊範圍標示為不安全。
  3. 掃描整個棋盤,找出安全的位置。

當然也可以在放置棋子和計算攻擊範圍的同時就計算出剩餘的空格數,因為題目只需回傳安全的位置數,不過這邊還是以比較容易理解的寫法實作。

語法

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

C#

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

namespace ChessCover
{
    class ChessCover
    {
        private int cols;
        private int rows;
        private Status[,] board;

        public int getSafe(string[] boardLayout)
        {
            rows = boardLayout.Length;
            cols = boardLayout[0].Length;

            board = new Status[rows, cols];
            for (int row = 0; row < rows; ++row)
                for (int col = 0; col < cols; ++col)
                    if (boardLayout[row][col] != 'U')
                        board[row, col] = Status.Piece;

            for (int row = 0; row < rows; ++row)
                for (int col = 0; col < cols; ++col)
                    switch (boardLayout[row][col])
                    {
                        case 'Q':
                            SetQueen(row, col);
                            break;
                        case 'R':
                            SetRock(row, col);
                            break;
                        case 'B':
                            SetBishop(row, col);
                            break;
                        case 'K':
                            SetKing(row, col);
                            break;
                        case 'P':
                            SetPawn(row, col);
                            break;
                    }

            int count = 0;
            for (int row = 0; row < rows; ++row)
                for (int col = 0; col < cols; ++col)
                    if (board[row, col] == Status.Safe)
                        ++count;

            return count;
        }

        private void SetQueen(int row, int col)
        {
            SetRock(row, col);
            SetBishop(row, col);
        }

        private void SetRock(int row, int col)
        {
            Trace(row, col, 0, 1);
            Trace(row, col, 1, 0);
            Trace(row, col, 0, -1);
            Trace(row, col, -1, 0);
        }

        private void SetBishop(int row, int col)
        {
            Trace(row, col, 1, 1);
            Trace(row, col, -1, -1);
            Trace(row, col, -1, 1);
            Trace(row, col, 1, -1);
        }

        private void SetKing(int row, int col)
        {
            SetUnsafe(row - 2, col - 1);
            SetUnsafe(row - 1, col - 2);
            SetUnsafe(row + 2, col + 1);
            SetUnsafe(row + 1, col + 2);
            SetUnsafe(row + 2, col - 1);
            SetUnsafe(row - 2, col + 1);
            SetUnsafe(row + 1, col - 2);
            SetUnsafe(row - 1, col + 2);
        }

        private void SetPawn(int row, int col)
        {
            SetUnsafe(row - 1, col - 1);
            SetUnsafe(row + 1, col - 1);
            SetUnsafe(row - 1, col + 1);
            SetUnsafe(row + 1, col + 1);
        }

        private void Trace(int row, int col, int offsetRow, int offsetCol)
        {
            for (int c = col + offsetCol, r = row + offsetRow; r < rows && c < cols && r >= 0 && c >= 0; r += offsetRow, c += offsetCol)
            {
                if (board[r, c] == Status.Piece)
                    break;
                board[r, c] = Status.Unsafe;
            }
        }

        private void SetUnsafe(int row, int col)
        {
            if (row < rows && col < cols && row >= 0 && col >= 0)
                if (board[row, col] == Status.Safe)
                    board[row, col] = Status.Unsafe;
        }

        enum Status
        {
            Safe,
            Unsafe,
            Piece
        }
    }
}

下載

VS2010 C# 版本

文章標籤
創作者介紹

小殘的程式光廊

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