可以被一步捕获的棋子数
难度:
标签:
题目描述
在一个 8 x 8 的棋盘上,有一个白色的车(Rook
),用字符 'R'
表示。棋盘上还可能存在空方块,白色的象(Bishop
)以及黑色的卒(pawn
),分别用字符 '.'
,'B'
和 'p'
表示。不难看出,大写字符表示的是白棋,小写字符表示的是黑棋。
车按国际象棋中的规则移动。东,西,南,北四个基本方向任选其一,然后一直向选定的方向移动,直到满足下列四个条件之一:
- 棋手选择主动停下来。
- 棋子因到达棋盘的边缘而停下。
- 棋子移动到某一方格来捕获位于该方格上敌方(黑色)的卒,停在该方格内。
- 车不能进入/越过已经放有其他友方棋子(白色的象)的方格,停在友方棋子前。
你现在可以控制车移动一次,请你统计有多少敌方的卒处于你的捕获范围内(即,可以被一步捕获的棋子数)。
示例 1:
输入:[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]] 输出:3 解释: 在本例中,车能够捕获所有的卒。
示例 2:
输入:[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]] 输出:0 解释: 象阻止了车捕获任何卒。
示例 3:
输入:[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]] 输出:3 解释: 车可以捕获位置 b5,d6 和 f5 的卒。
提示:
board.length == board[i].length == 8
board[i][j]
可以是'R'
,'.'
,'B'
或'p'
- 只有一个格子上存在
board[i][j] == 'R'
代码结果
运行时间: 25 ms, 内存: 16.1 MB
// Solution using Java Streams
// In this solution, we'll use the Stream API to simulate the movements
// of the Rook in all four directions. However, note that streams in Java
// are typically not used for this type of grid traversal due to their
// stateless nature and the imperative nature of the task.
// Here, we're illustrating how to use streams but it's not the best use case.
import java.util.stream.IntStream;
public class RookCaptureStream {
public int numRookCaptures(char[][] board) {
int[] rookPos = findRook(board);
return IntStream.of(
countCaptures(board, rookPos, -1, 0), // Up
countCaptures(board, rookPos, 1, 0), // Down
countCaptures(board, rookPos, 0, -1), // Left
countCaptures(board, rookPos, 0, 1) // Right
).sum();
}
private int[] findRook(char[][] board) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board[i][j] == 'R') {
return new int[]{i, j};
}
}
}
return null;
}
private int countCaptures(char[][] board, int[] rookPos, int rowDir, int colDir) {
int x = rookPos[0], y = rookPos[1];
while (true) {
x += rowDir;
y += colDir;
if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B') break;
if (board[x][y] == 'p') return 1;
}
return 0;
}
}
解释
方法:
该题解的主要思路是首先将棋盘的行和列转化为字符串形式,然后组合到一起,形成一个单一的长字符串。接着,通过删除所有表示空格的'.'字符,使得字符串中只剩下棋子的字符。这样,'pR'和'Rp'将直接表示车(Rook)能够捕获的黑卒(pawn)的情况,即这两种组合分别代表黑卒在车的左侧或右侧,上侧或下侧。最后,统计这两种组合在字符串中出现的次数之和,即为答案。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在构建行和列的信息时选择使用字符串而不是其他数据结构如列表或数组?
▷🦆
在合并行和列信息后,为什么要选择移除所有的'.'字符,这一步有什么特殊的意义或优势?
▷🦆
给出的算法中如何确保'Rook'(车)与'pawn'(卒)之间没有被其他棋子阻挡,特别是考虑到有'Bishop'(象)也可能位于它们之间的情形?
▷🦆
在题解中提到使用逗号','作为分隔符,这是否可能引起解析上的混淆或错误,特别是当棋盘配置复杂时?
▷