# LeetCode 999: Available Captures for Rook

## Problem Restatement

We are given an `8 x 8` chessboard.

Each cell contains one of four characters:

| Character | Meaning |
|---|---|
| `"R"` | White rook |
| `"B"` | White bishop |
| `"p"` | Black pawn |
| `"."` | Empty square |

There is exactly one rook.

The rook can move horizontally or vertically. It can capture a pawn if the pawn is the first piece in that direction.

The rook cannot move through another piece. A bishop blocks the rook, and a pawn also stops the rook after being captured.

We need to return the number of pawns the rook can capture in one move. The official statement defines the rook movement in four cardinal directions and notes that pieces block its path.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `8 x 8` board |
| Output | Number of pawns the rook can capture |
| Rook | `"R"` |
| Bishop | `"B"` blocks movement |
| Pawn | `"p"` can be captured if visible |
| Empty cell | `"."` |

Function shape:

```python
def numRookCaptures(board: list[list[str]]) -> int:
    ...
```

## Examples

Example 1:

```python
board = [
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
]
```

The rook is at row `2`, column `3`.

It can capture:

| Direction | First piece seen | Result |
|---|---|---|
| Up | Pawn | Capture |
| Down | Pawn | Capture |
| Left | No piece | No capture |
| Right | Pawn | Capture |

Answer:

```python
3
```

Example 2:

```python
board = [
    [".",".",".",".",".",".",".","."],
    [".","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",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
]
```

The rook is blocked by bishops in all four directions.

Answer:

```python
0
```

## First Thought: Simulate the Rook

The board is small and fixed at `8 x 8`.

So we can directly simulate how a rook moves:

1. Find the rook.
2. Look upward until hitting a piece or leaving the board.
3. Look downward.
4. Look left.
5. Look right.
6. Count the first pawn visible in each direction.

This matches the chess rule exactly.

## Key Insight

Only the first non-empty square in each direction matters.

If the first piece is a pawn, the rook can capture it.

If the first piece is a bishop, the rook is blocked.

If there is no piece before the board edge, there is no capture.

So each direction contributes either `0` or `1`.

## Algorithm

First scan the board to find the rook position:

```python
rook_row, rook_col
```

Then define four directions:

```python
up, down, left, right
```

For each direction:

1. Start one square away from the rook.
2. Move while inside the board.
3. If the cell is `"."`, continue.
4. If the cell is `"p"`, increment the answer and stop this direction.
5. If the cell is `"B"`, stop this direction.

Return the answer.

## Correctness

The algorithm first finds the unique rook position.

For each of the four legal rook directions, it scans squares in the exact order the rook would encounter them while moving. Empty squares do not affect movement, so the scan continues through them.

When the scan reaches a pawn, that pawn is the first piece in that direction, so the rook can capture it in one move. The algorithm counts it and stops, because the rook cannot move beyond the captured pawn.

When the scan reaches a bishop, the bishop blocks the rook, so no pawn beyond it can be captured in that direction. The algorithm stops without counting.

If the scan reaches the board edge without seeing a pawn, then no capture is possible in that direction.

Since the rook can only move in these four directions, and the algorithm checks each direction exactly once, the returned count is correct.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | The board is always `8 x 8` |
| Space | `O(1)` | Only a few variables are stored |

If generalized to an `n x n` board, the time would be `O(n^2)` to find the rook and `O(n)` to scan directions.

## Implementation

```python
class Solution:
    def numRookCaptures(self, board: list[list[str]]) -> int:
        rook_row = -1
        rook_col = -1

        for r in range(8):
            for c in range(8):
                if board[r][c] == "R":
                    rook_row = r
                    rook_col = c
                    break

            if rook_row != -1:
                break

        captures = 0
        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        for dr, dc in directions:
            r = rook_row + dr
            c = rook_col + dc

            while 0 <= r < 8 and 0 <= c < 8:
                if board[r][c] == "p":
                    captures += 1
                    break

                if board[r][c] == "B":
                    break

                r += dr
                c += dc

        return captures
```

## Code Explanation

We first locate the rook:

```python
for r in range(8):
    for c in range(8):
        if board[r][c] == "R":
            rook_row = r
            rook_col = c
            break
```

After the rook is found, we scan four directions:

```python
directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]
```

Each direction uses a row delta and a column delta.

For example:

```python
(1, 0)
```

moves downward one row at a time.

The scan continues while the position is inside the board:

```python
while 0 <= r < 8 and 0 <= c < 8:
```

If the first piece is a pawn, count one capture:

```python
if board[r][c] == "p":
    captures += 1
    break
```

If the first piece is a bishop, stop without counting:

```python
if board[r][c] == "B":
    break
```

Otherwise the square is empty, so continue moving:

```python
r += dr
c += dc
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numRookCaptures([
        [".",".",".",".",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".","R",".",".",".","p"],
        [".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".",".",".",".",".","."],
        [".",".",".",".",".",".",".","."],
    ]) == 3

    assert s.numRookCaptures([
        [".",".",".",".",".",".",".","."],
        [".","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

    assert s.numRookCaptures([
        [".",".",".",".",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        ["p","p",".","R",".","p","B","."],
        [".",".",".",".",".",".",".","."],
        [".",".",".","B",".",".",".","."],
        [".",".",".","p",".",".",".","."],
        [".",".",".",".",".",".",".","."],
    ]) == 3

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| First board | `3` | Rook sees three pawns |
| Bishop-blocked board | `0` | Bishops block all directions |
| Mixed board | `3` | Captures first visible pawns only |