# Available Captures for Rook
**Difficulty:** EASY
[External](https://leetcode.com/problems/available-captures-for-rook)
Canonical: https://scaleengineer.com/dsa/problems/available-captures-for-rook
**Data structures:** Array, Matrix
**Companies:** [Block](https://scaleengineer.com/companies/block)
---
## Problem
You are given an `8 x 8` **matrix** representing a chessboard. There is **exactly one** white rook represented by `'R'`, some number of white bishops `'B'`, and some number of black pawns `'p'`. Empty squares are represented by `'.'`.

A rook can move any number of squares horizontally or vertically (up, down, left, right) until it reaches another piece _or_ the edge of the board. A rook is **attacking** a pawn if it can move to the pawn's square in one move.

Note: A rook cannot move through other pieces, such as bishops or pawns. This means a rook cannot attack a pawn if there is another piece blocking the path.

Return the **number of pawns** the white rook is **attacking**.

**Example 1:**

![](https://assets.glich.co/dsa/available-captures-for-rook/image0.PNG) 

**Input:** board = \[\[".",".",".",".",".",".",".","."\],\[".",".",".","p",".",".",".","."\],\[".",".",".","R",".",".",".","p"\],\[".",".",".",".",".",".",".","."\],\[".",".",".",".",".",".",".","."\],\[".",".",".","p",".",".",".","."\],\[".",".",".",".",".",".",".","."\],\[".",".",".",".",".",".",".","."\]\]

**Output:** 3

**Explanation:**

In this example, the rook is attacking all the pawns.

**Example 2:**

![](https://assets.glich.co/dsa/available-captures-for-rook/image1.PNG) 

**Input:** 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",".","."\],\[".",".",".",".",".",".",".","."\],\[".",".",".",".",".",".",".","."\]\]

**Output:** 0

**Explanation:**

The bishops are blocking the rook from attacking any of the pawns.

**Example 3:**

![](https://assets.glich.co/dsa/available-captures-for-rook/image2.PNG) 

**Input:** board = \[\[".",".",".",".",".",".",".","."\],\[".",".",".","p",".",".",".","."\],\[".",".",".","p",".",".",".","."\],\["p","p",".","R",".","p","B","."\],\[".",".",".",".",".",".",".","."\],\[".",".",".","B",".",".",".","."\],\[".",".",".","p",".",".",".","."\],\[".",".",".",".",".",".",".","."\]\]

**Output:** 3

**Explanation:**

The rook is attacking the pawns at positions b5, d6, and f5.

**Constraints:**

* `board.length == 8`
* `board[i].length == 8`
* `board[i][j]` is either `'R'`, `'.'`, `'B'`, or `'p'`
* There is exactly one cell with `board[i][j] == 'R'`

# Approaches
## Pawn-Centric Path Checking
This approach first identifies the locations of the rook and all pawns. It then iterates through each pawn, checking if it's on the same row or column as the rook and if the path between them is unobstructed. This method is less efficient due to redundant checks and higher memory usage.
**Time:** O(N^2 + k*N), where N is the board dimension (8) and k is the number of pawns. The initial scan is O(N^2). Then, for each of the `k` pawns, we might scan up to N cells to check the path. For a fixed 8x8 board, this is constant time, but it's computationally heavier than the optimal approach. · **Space:** O(k), where `k` is the number of pawns. We need to store the coordinates of all pawns. In the worst case, this could be O(N^2) if most of the board is filled with pawns.
**Pros:** Separates the logic of finding pieces from checking captures, which can be clear for some developers.
**Cons:** Inefficient due to repeated scanning of rows/columns.; Requires extra space to store pawn locations.; More complex logic for checking paths between two points.
### Explanation
The core idea is to check, for every pawn, whether it is vulnerable to capture by the rook. The algorithm proceeds in two main phases:

1.  **Piece Location**: The entire 8x8 board is scanned to find the coordinates of the white rook ('R') and to build a list containing the coordinates of every black pawn ('p').

2.  **Capture Verification**: The algorithm then iterates through the list of pawns. For each pawn, it checks two conditions:
    *   Is the pawn on the same row or column as the rook?
    *   If so, is the path between the rook and the pawn clear of any other pieces (bishops or other pawns)?

To check the path, a loop iterates over the squares between the rook and the pawn. If any of these squares is not empty ('.'), the path is blocked, and the pawn cannot be captured. If the path is clear, a capture counter is incremented. This process is repeated for all pawns.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int numRookCaptures(char[][] board) {
        int rookRow = -1, rookCol = -1;
        List<int[]> pawnPositions = new ArrayList<>();

        // Phase 1: Find Rook and all Pawns
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                } else if (board[i][j] == 'p') {
                    pawnPositions.add(new int[]{i, j});
                }
            }
        }

        int captures = 0;
        // Phase 2: For each pawn, check if it's capturable
        for (int[] pawnPos : pawnPositions) {
            int pRow = pawnPos[0];
            int pCol = pawnPos[1];

            if (pRow == rookRow) { // Same row
                boolean pathClear = true;
                int startCol = Math.min(pCol, rookCol) + 1;
                int endCol = Math.max(pCol, rookCol);
                for (int c = startCol; c < endCol; c++) {
                    if (board[rookRow][c] != '.') {
                        pathClear = false;
                        break;
                    }
                }
                if (pathClear) {
                    captures++;
                }
            } else if (pCol == rookCol) { // Same column
                boolean pathClear = true;
                int startRow = Math.min(pRow, rookRow) + 1;
                int endRow = Math.max(pRow, rookRow);
                for (int r = startRow; r < endRow; r++) {
                    if (board[r][rookCol] != '.') {
                        pathClear = false;
                        break;
                    }
                }
                if (pathClear) {
                    captures++;
                }
            }
        }
        return captures;
    }
}
```
### Algorithm
- Iterate through the `8x8` board to find the coordinates of the rook `(rookRow, rookCol)` and to build a list of all pawn coordinates.
- Initialize a `captures` count to 0.
- Iterate through the list of pawn coordinates.
- For each pawn at `(pRow, pCol)`:
  - If `pRow == rookRow`, check the horizontal path between the pawn and the rook. If no other pieces are found, increment `captures`.
  - If `pCol == rookCol`, check the vertical path between the pawn and the rook. If no other pieces are found, increment `captures`.
- Return the final `captures` count.

## Optimized Rook-Centric Search
This optimal approach first locates the rook and then simulates its movement in the four cardinal directions (up, down, left, right). It scans outwards from the rook's position, stopping in a given direction as soon as any piece is encountered. If the piece is a pawn, it's counted as a capture. This avoids redundant checks and uses minimal memory.
**Time:** O(N^2), where N is the board dimension (8). The search for the rook takes O(N^2) in the worst case. The subsequent search in four directions takes at most O(4*N) steps. The total complexity is dominated by the initial search. For a fixed 8x8 board, this is constant time, O(1). · **Space:** O(1). The algorithm uses only a few variables to store the rook's position, the capture count, and loop counters, regardless of the board's content.
**Pros:** Optimal time complexity as it avoids redundant checks.; Minimal space usage (O(1)).; The logic is clean and directly simulates the rook's movement.
**Cons:** No significant disadvantages for this problem; it is the standard and most efficient solution.
### Explanation
This algorithm directly simulates the rook's behavior on a chessboard, making it highly intuitive and efficient.

1.  **Find the Rook**: The first step is a single pass over the board to find the `(row, col)` coordinates of the rook, 'R'. The loops can be terminated as soon as the rook is found.

2.  **Scan in Four Directions**: Once the rook is located, the algorithm checks for captures along the four cardinal directions. This can be elegantly handled using a directions array (e.g., `{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}` for up, down, left, right). For each direction:
    *   A loop starts from the rook's position and moves one step at a time in the current direction.
    *   The loop continues as long as it stays within the board's boundaries.
    *   At each square, the piece is checked. If it's a pawn 'p', the capture count is incremented, and the loop for this direction terminates (since the path is now blocked).
    *   If it's a bishop 'B', the loop for this direction also terminates, but no capture is counted.
    *   If the square is empty '.', the loop continues to the next square in the same direction.

This method ensures that each of the four paths from the rook is traversed only once, making it the most efficient solution.

```java
class Solution {
    public int numRookCaptures(char[][] board) {
        int rookRow = 0, rookCol = 0;
        // 1. Find the Rook
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    rookRow = i;
                    rookCol = j;
                    break;
                }
            }
        }

        int captures = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // Up, Down, Left, Right

        // 2. Scan in four directions
        for (int[] d : directions) {
            int r = rookRow + d[0];
            int c = rookCol + d[1];
            while (r >= 0 && r < 8 && c >= 0 && c < 8) {
                if (board[r][c] == 'p') {
                    captures++;
                    break; // Stop searching in this direction
                }
                if (board[r][c] == 'B') {
                    break; // Stop searching in this direction
                }
                r += d[0];
                c += d[1];
            }
        }
        return captures;
    }
}
```
### Algorithm
- Iterate through the `8x8` board to find the coordinates of the rook `(rookRow, rookCol)`.
- Initialize a `captures` count to 0.
- Define the four cardinal directions (e.g., using an array of coordinate changes like `{{-1,0}, {1,0}, {0,-1}, {0,1}}`).
- For each of the four directions:
  - Start from the square adjacent to the rook and move one step at a time in the current direction.
  - Continue moving until you go off the board or encounter another piece.
  - If the first piece encountered is a pawn 'p', increment `captures`.
  - After finding any piece (pawn or bishop), stop searching in that direction and move to the next one.
- Return the final `captures` count.

# Solutions
### Java

```java
class Solution {
public
  int numRookCaptures(char[][] board) {
    int ans = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int i = 0; i < 8; ++i) {
      for (int j = 0; j < 8; ++j) {
        if (board[i][j] == 'R') {
          for (int k = 0; k < 4; ++k) {
            int x = i, y = j;
            int a = dirs[k], b = dirs[k + 1];
            while (x + a >= 0 && x + a < 8 && y + b >= 0 && y + b < 8 &&
                   board[x + a][y + b] != 'B') {
              x += a;
              y += b;
              if (board[x][y] == 'p') {
                ++ans;
                break;
              }
            }
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numRookCaptures(vector<vector<char>> &board) {
    int ans = 0;
    int dirs[5] = {-1, 0, 1, 0, -1};
    for (int i = 0; i < 8; ++i) {
      for (int j = 0; j < 8; ++j) {
        if (board[i][j] == 'R') {
          for (int k = 0; k < 4; ++k) {
            int x = i, y = j;
            int a = dirs[k], b = dirs[k + 1];
            while (x + a >= 0 && x + a < 8 && y + b >= 0 && y + b < 8 &&
                   board[x + a][y + b] != 'B') {
              x += a;
              y += b;
              if (board[x][y] == 'p') {
                ++ans;
                break;
              }
            }
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int: ans = 0 dirs = (- 1, 0, 1, 0, - 1) for i in range(8): for j in range(8): if board[i][j] == "R": for a, b in pairwise(dirs): x, y = i, j while 0 <= x + a < 8 and 0 <= y + b < 8: x, y = x + a, y + b if board[x][y] == "p": ans += 1 break if board[x][y] == "B": break return ans

```