程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1484 . 角力棋
TopCoder
Tags
Description
角力棋（Abalone）在正六邊形棋盤上進行，棋盤邊長為 $n$，共 $3n^ 2 - 3n + 1$ 格，每格為空格、黑子或白子之一。
棋盤的 $2n-1$ 列由上而下、靠左對齊，長度依序為 $n, n+1, \dots, 2n-1, \dots, n+1, n$（中間列最長）；置中後排成一個正六邊形，如下圖（以 $n = 3$ 為例）：
每個格子（邊界上的除外）都有 $6$ 個相鄰格，沿三條軸線、每條兩個方向（見上圖）。
本題只看黑方的推移，定義為：「挑一段在同一軸線上連續相鄰的黑子，沿該線方向把整段往前推一格（六個方向之一）」。
一段黑子能推動白子，須同時滿足下列三條件（否則不會有白子被推動）：
- 黑子正前方緊接一段連續白子
- 移動的黑子數嚴格多於該段白子數
- 該段白子正後方一格為空格或在棋盤外
兩種推移只要方向、所移動的棋子、或移動的棋子數任一不同，即視為不同推移。
每筆輸入包含 $T$ 個彼此獨立的盤面，對每個盤面，求所有從初始盤面恰進行一次推移之中，會使至少一顆白子被移動的相異推移數。
Input Format
第一行有一個整數 $T$，代表盤面數量。
接下來描述 $T$ 個盤面。每個盤面：
- 先有一行包含一個整數 $n$，代表六邊形棋盤的邊長；
接著有 $2n-1$ 行，靠左對齊、不含多餘空白地描述六邊形的各個橫列。第 $r$ 行（$0$ 起始）的長度依序為 $n, n+1, \dots, 2n-1, \dots, n+1, n$（中間最長）。每個字元為下列三者之一：
.（空格）、B（黑子）、W（白子）。$1 \le T \le 10^ 4$
$1 \le n \le 100$
$\sum (3n^ 2 - 3n + 1) \le 3 \times 10^ 6$
Output Format
對每個盤面輸出一行，包含一個整數，代表恰進行一次推移、會使至少一顆白子被移動的相異黑方推移數量。
Sample Input 1
2 3 ... .... BBW.. .... ... 1 B
Sample Output 1
1 0
Sample Input 2
1 3 ... .... BBBBW .... ...
Sample Output 2
3
Sample Input 3
1 3 ... .... WBBWB .... ...
Sample Output 3
1
Hints
範例 1
第一個盤面（$n = 3$）對齊後的樣子為：
. . .
. . . .
B B W . .
. . . .
. . .
中間列是 B B W . .。兩顆黑子可以把那顆白子往右推進旁邊的空格；由於黑子只有兩顆，能用的推移就只有「兩顆一起推」這 $1$ 種，其他方向都動不了白子。所以答案為 $1$。
第二個盤面（$n = 1$）只有一格：
B
只有一格，無法形成任何推移，答案為 $0$。
範例 2
盤面（$n = 3$）對齊後的樣子為：
. . .
. . . .
B B B B W
. . . .
. . .
中間列是 B B B B W，四顆黑子後面接著一顆位於右邊界的白子。黑方可以選用 $2$ 顆、$3$ 顆或 $4$ 顆黑子，把這顆白子推出棋盤外。選用的黑子數不同算作不同推移，所以共 $3$ 種。
範例 3
盤面（$n = 3$）對齊後的樣子為：
. . .
. . . .
W B B W B
. . . .
. . .
中間列是 W B B W B。看起來有數個黑白相鄰之處，但只有一種是合法推移：位置 $2$、$3$ 的兩顆黑子，可以把最左邊那顆白子（位置 $1$）往左推出盤外。至於位置 $4$ 的白子，無論往左或往右推，它正後方那一格都被黑子占住，所以不能推。因此答案為 $1$。
Problem Source
2026 YTP 高中組初賽 p4
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測試資料 | 0 |
| 2 | 3~11 | 所有會使白子移動的推移都沿橫軸（沿同一橫列） | 4 |
| 3 | 12~20 | 所有會使白子移動的推移都沿橫軸或「左下到右上」斜軸（沒有「左上到右下」斜軸的推移） | 4 |
| 4 | 3~43 | 無額外限制 | 2 |