Available Captures for Rook — Easy Problem & Solution

Problem statement

An 8 × 8 chessboard is given as 8 strings of 8 characters. It holds exactly one white rook 'R', any number of white bishops 'B' and black pawns 'p', and '.' for empty squares.

The rook moves any number of squares straight up, down, left or right, stopping at the first piece in its way or the edge of the board. It attacks a pawn when the pawn is the first piece it meets in one of those four directions; a bishop (its own piece) blocks the line.

Return the number of pawns the rook attacks.

Example 1

Input: board = ["........","...p....","...R..p.","........","........","...p....","........","........"]
Output: 3
Explanation: The pawns straight above, to the right of and below the rook are all reachable.

Example 2

Input: board = ["........","...p....","...B....",".pBR.Bp.","........","...p....","........","........"]
Output: 1
Explanation: Bishops block the rook upwards, to the left and to the right; only the pawn below is attacked.

Example 3

Input: board = ["R.......","........","........","........","........","........","........","........"]
Output: 0

Constraints

• board.length == 8
• board[i].length == 8
• board[i][j] is 'R', '.', 'B' or 'p'
• there is exactly one 'R'

How to solve Available Captures for Rook

The rook attacks at most one piece per direction — the first non-empty square — so four short walks settle it.

Approach

1. Locate 'R'.
2. For each of the four directions, step from the rook while inside the board and on '.'.
3. If the walk stopped on a 'p', add one; if it stopped on a 'B' or left the board, add nothing.

Why it works

A rook's line of attack ends at the first occupied square, so the only pawn it can capture in a direction is the one on that square. Checking all four directions covers every possible capture.

Complexity

• Time — O(1) — at most 28 squares are visited on an 8 × 8 board
• Space — O(1)

Pitfalls

• A bishop blocks the line even though it is on the rook's side — pawns behind it are safe.
• Pawns on a diagonal from the rook cannot be attacked.
• Only the first pawn in a direction counts, even if several are in line.

Reference solution

Python

from typing import List

def numRookCaptures(board: List[str]) -> int:
    r0 = c0 = 0
    for i in range(8):
        for j in range(8):
            if board[i][j] == 'R':
                r0, c0 = i, j
    caps = 0
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        r, c = r0 + dr, c0 + dc
        while 0 <= r < 8 and 0 <= c < 8 and board[r][c] == '.':
            r += dr
            c += dc
        if 0 <= r < 8 and 0 <= c < 8 and board[r][c] == 'p':
            caps += 1
    return caps

JavaScript

var numRookCaptures = function(board) {
    var r0 = 0, c0 = 0;
    for (var i = 0; i < 8; i++) for (var j = 0; j < 8; j++) if (board[i][j] === 'R') { r0 = i; c0 = j; }
    var dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]], caps = 0;
    for (var d = 0; d < 4; d++) {
        var r = r0 + dirs[d][0], c = c0 + dirs[d][1];
        while (r >= 0 && c >= 0 && r < 8 && c < 8 && board[r][c] === '.') { r += dirs[d][0]; c += dirs[d][1]; }
        if (r >= 0 && c >= 0 && r < 8 && c < 8 && board[r][c] === 'p') caps++;
    }
    return caps;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Delete Columns to Make Sorted Easy
• Maximize Sum Of Array After K Negations Easy
• Nearest Smaller Element Easy
• Minimum Positive Sum Subarray Easy
• Find X-Sum of All K-Long Subarrays I Easy
• Valid Boomerang Easy