資訊

  • 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ ChessCover
  • 分數：1000

題目

說明

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

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

如下圖所示：

1
2
3
4
5
6
7
8
    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  + + + + + + +  + + + + + + +

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

  • U：表示沒有棋子。
  • Q：表示 Queen。
  • R：表示 Rook。
  • B：表示 Bishop。
  • K：表示 Knight。
  • P：表示 Pawn。

注意

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

程式介面

1
2
3
4
5
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。

範例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
輸入：
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. 掃描整個棋盤，找出安全的位置。

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

語法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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
        }
    }
}

延伸閱讀

上一題 TopCoder Inv 2001 Semi A+B - Tothello
TopCoder - 線上程式設計競賽