# LeetCode 419: Battleships in a Board

## Problem Restatement

We are given a 2D board containing:

| Character | Meaning |
|---|---|
| `"X"` | Part of a battleship |
| `"."` | Empty water |

Battleships follow these rules:

1. Battleships are placed either horizontally or vertically.
2. Battleships cannot touch each other horizontally, vertically, or diagonally.
3. A battleship consists of one or more consecutive `"X"` cells.

Return the total number of battleships on the board.

The official follow-up asks whether we can solve the problem in one pass using only constant extra memory and without modifying the board. The constraints allow up to `200 x 200` boards. ([leetcode.com](https://leetcode.com/problems/battleships-in-a-board/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | 2D board of `"X"` and `"."` |
| Output | Number of battleships |
| Ship orientation | Horizontal or vertical only |
| Separation rule | Ships never touch each other |

Example function shape:

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

## Examples

Example 1:

image_group{"layout":"carousel","aspect_ratio":"16:9","query":["leetcode 419 battleships in a board example","battleship board grid example","count battleships matrix illustration","horizontal and vertical battleship example"],"num_per_query":1}

```python
board = [
    ["X", ".", ".", "X"],
    [".", ".", ".", "X"],
    [".", ".", ".", "X"],
]
```

The answer is:

```python
2
```

Explanation:

| Battleship | Cells |
|---|---|
| Horizontal/Single | `(0,0)` |
| Vertical | `(0,3), (1,3), (2,3)` |

Example 2:

```python
board = [["."]]
```

The answer is:

```python
0
```

Example 3:

```python
board = [["X"]]
```

The answer is:

```python
1
```

## First Thought: DFS or BFS

One natural approach is:

1. Scan the grid.
2. When we find an unvisited `"X"`, start DFS or BFS.
3. Mark the whole ship as visited.
4. Increment the answer.

This works.

But the problem guarantees ships never touch each other.

That allows a simpler one-pass solution with constant extra space.

## Key Insight

Every battleship has exactly one top-left starting cell.

For example:

```text
X X X
```

The first cell is the ship start.

The later cells belong to the same ship.

Similarly:

```text
X
X
X
```

Again, only the top cell is the start.

So while scanning the board:

A cell starts a new battleship exactly when:

1. The cell contains `"X"`.
2. There is no `"X"` directly above it.
3. There is no `"X"` directly to its left.

That means this cell is the top-left corner of a ship.

Every battleship contributes exactly one such cell.

## Algorithm

Initialize:

```python
count = 0
```

Scan every cell `(r, c)`.

For each cell:

1. If the cell is `"."`, skip it.
2. If the cell above is `"X"`, skip it.
3. If the cell to the left is `"X"`, skip it.
4. Otherwise, this cell is the start of a new battleship:
   - Increment `count`.

Return `count`.

## Correctness

Consider any battleship on the board.

Because ships are straight horizontal or vertical segments, the battleship has exactly one top-leftmost cell.

For that cell:

1. There is no `"X"` above it.
2. There is no `"X"` to its left.

Therefore, the algorithm counts that cell.

Now consider any other cell belonging to the same battleship.

If the ship is horizontal, then that cell has an `"X"` to its left.

If the ship is vertical, then that cell has an `"X"` above it.

So the algorithm skips every non-start cell.

Thus each battleship is counted exactly once.

Since every counted cell corresponds to a unique battleship start, and every battleship has exactly one such start cell, the final count is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(mn)` | Every cell is visited once |
| Space | `O(1)` | Only a counter is used |

Here:

| Symbol | Meaning |
|---|---|
| `m` | Number of rows |
| `n` | Number of columns |

## Implementation

```python
from typing import List

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        rows = len(board)
        cols = len(board[0])

        count = 0

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == ".":
                    continue

                if r > 0 and board[r - 1][c] == "X":
                    continue

                if c > 0 and board[r][c - 1] == "X":
                    continue

                count += 1

        return count
```

## Code Explanation

We first get the board size:

```python
rows = len(board)
cols = len(board[0])
```

The variable:

```python
count
```

stores the number of battleships found.

We scan every cell:

```python
for r in range(rows):
    for c in range(cols):
```

If the cell is empty water:

```python
if board[r][c] == ".":
    continue
```

then it cannot start a battleship.

If the cell above is part of a ship:

```python
if r > 0 and board[r - 1][c] == "X":
    continue
```

then the current cell belongs to the same vertical ship.

If the cell to the left is part of a ship:

```python
if c > 0 and board[r][c - 1] == "X":
    continue
```

then the current cell belongs to the same horizontal ship.

If neither condition holds, this cell is the unique top-left start of a battleship:

```python
count += 1
```

Finally:

```python
return count
```

returns the total number of ships.

## Alternative DFS Solution

A DFS approach also works.

```python
from typing import List

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        rows = len(board)
        cols = len(board[0])

        visited = [[False] * cols for _ in range(rows)]

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return

            if board[r][c] != "X":
                return

            if visited[r][c]:
                return

            visited[r][c] = True

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        ships = 0

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "X" and not visited[r][c]:
                    ships += 1
                    dfs(r, c)

        return ships
```

This version is easier to generalize, but it uses additional memory.

## Testing

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

    board1 = [
        ["X", ".", ".", "X"],
        [".", ".", ".", "X"],
        [".", ".", ".", "X"],
    ]

    assert s.countBattleships(board1) == 2

    board2 = [["."]]

    assert s.countBattleships(board2) == 0

    board3 = [["X"]]

    assert s.countBattleships(board3) == 1

    board4 = [
        ["X", "X", ".", "X"],
        [".", ".", ".", "."],
        ["X", ".", "X", "X"],
    ]

    assert s.countBattleships(board4) == 4

    board5 = [
        ["X"],
        ["X"],
        ["X"],
    ]

    assert s.countBattleships(board5) == 1

    print("all tests passed")
```

## Test Notes

| Test | Why |
|---|---|
| Standard example | Mixed single and vertical ships |
| Empty board | No ships |
| Single-cell ship | Smallest battleship |
| Multiple separated ships | Checks counting logic |
| Vertical ship | Ensures only top cell is counted |