# Battleships in a Board
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/battleships-in-a-board)
Canonical: https://scaleengineer.com/dsa/problems/battleships-in-a-board
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Microstrategy](https://scaleengineer.com/companies/microstrategy)
---
## Problem
Given an `m x n` matrix `board` where each cell is a battleship `'X'` or empty `'.'`, return _the number of the **battleships** on_ `board`.

**Battleships** can only be placed horizontally or vertically on `board`. In other words, they can only be made of the shape `1 x k` (`1` row, `k` columns) or `k x 1` (`k` rows, `1` column), where `k` can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).

**Example 1:**

![](https://assets.glich.co/dsa/battleships-in-a-board/image0.png) 

**Input:** board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
**Output:** 2

**Example 2:**

**Input:** board = [["."]]
**Output:** 0

**Constraints:**

* `m == board.length`
* `n == board[i].length`
* `1 <= m, n <= 200`
* `board[i][j]` is either `'.'` or `'X'`.

**Follow up:** Could you do it in one-pass, using only `O(1)` extra memory and without modifying the values `board`?

# Approaches
## DFS Traversal (Sink the Ship)
A standard approach for counting connected components in a grid is to use a graph traversal algorithm like Depth First Search (DFS) or Breadth First Search (BFS). We can treat the grid as a graph where each 'X' is a node and adjacent 'X's have an edge between them. The goal is to count the number of disconnected subgraphs of 'X's.

The algorithm iterates through each cell of the board. If it finds a cell with an 'X' that hasn't been visited yet, it means we've discovered a new battleship. We increment our battleship counter. Then, we start a traversal (DFS) from that cell to find all other 'X's belonging to the same ship. During the traversal, we mark each visited 'X' (e.g., by changing it to '.') to ensure we don't count any part of this ship again. This process is often called "sinking the ship". We continue scanning the grid until all cells have been checked.
**Time:** O(m * n), where `m` and `n` are the dimensions of the board. The nested loops iterate through each cell once. The DFS traversal also visits each 'X' cell at most once over the entire execution. Therefore, every cell is processed a constant number of times. · **Space:** O(m * n) in the worst case. This space is consumed by the recursion stack. For a board filled with a single, long, winding battleship, the recursion depth could be proportional to the total number of cells. If a separate `visited` matrix is used instead of in-place modification, it also requires `O(m * n)` space.
**Pros:** The logic is straightforward and a standard application of graph traversal.; It's robust and would work even if battleships had more complex shapes (e.g., 'L' or 'T' shapes), as long as they are contiguous.
**Cons:** This approach modifies the input board, which might not be permissible in some contexts.; If modification is not allowed, a separate `visited` matrix of size `m x n` is required, leading to `O(m * n)` space complexity.; The recursion depth can, in the worst-case scenario (a long, snake-like ship), be up to `O(m * n)`, potentially leading to a stack overflow for very large boards.
### Explanation
```java
class Solution {
    public int countBattleships(char[][] board) {
        if (board == null || board.length == 0) {
            return 0;
        }
        int m = board.length;
        int n = board[0].length;
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    count++;
                    dfs(board, i, j);
                }
            }
        }
        
        // Note: This approach modifies the board. To restore it, one would need to 
        // store the original 'X' positions and change them back, which adds complexity.

        return count;
    }

    private void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;

        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'X') {
            return;
        }

        // Mark the current cell as visited by changing it to '.'
        board[i][j] = '.';

        // Explore neighbors
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}
```
### Algorithm
1. Initialize a battleship counter `count` to 0.
2. Get the dimensions of the board, `m` rows and `n` columns.
3. Iterate through each cell `(i, j)` of the board from `(0, 0)` to `(m-1, n-1)`.
4. If the current cell `board[i][j]` contains an 'X':
   a. Increment the `count`.
   b. Start a Depth First Search (DFS) from this cell to find all connected 'X's that form the complete battleship.
   c. The DFS function, `dfs(board, r, c)`, works as follows:
      i. Check for base cases: if the coordinates `(r, c)` are out of bounds or if `board[r][c]` is not 'X', return.
      ii. Mark the current cell as visited to prevent recounting. A common way is to change `board[r][c]` to '.' (this modifies the input board).
      iii. Recursively call `dfs` for all four adjacent cells: `(r+1, c)`, `(r-1, c)`, `(r, c+1)`, and `(r, c-1)`.
5. After the nested loops complete, return the final `count`.

## Single Pass Counting
This optimal approach solves the problem in a single pass over the board, using only constant extra memory and without modifying the input array. It perfectly addresses the follow-up question.

The key insight is to count each battleship exactly once by identifying a unique, representative cell for each ship. A convenient choice is the "head" of the ship, which we can define as its top-most, left-most 'X'.

As we iterate through the grid, whenever we encounter an 'X', we simply check if it's a head. An 'X' at `(i, j)` is a head if there is no 'X' immediately above it (`board[i-1][j]`) and no 'X' immediately to its left (`board[i][j-1]`). If it is a head, we increment our count. If not, it's part of a ship we've already counted (or will count when we reach its head), so we ignore it. This ensures every ship is counted precisely once.
**Time:** O(m * n). We iterate through every cell of the grid exactly once, performing a constant number of checks for each cell. · **Space:** O(1). The algorithm only uses a few variables for the count and loop indices, which does not depend on the size of the input board.
**Pros:** Extremely efficient, with optimal time and space complexity.; Achieves the solution in a single pass over the grid.; Uses only `O(1)` extra space.; Does not modify the input board, which is a common requirement.; The implementation is simple and avoids recursion.
**Cons:** The logic is highly specific to the problem's constraints, namely that battleships are straight lines (1xK or Kx1) and are always separated by at least one empty cell. It would not work for more complex ship shapes or if ships could be adjacent.
### Explanation
```java
class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length;
        if (m == 0) {
            return 0;
        }
        int n = board[0].length;
        
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Skip empty cells
                if (board[i][j] == '.') {
                    continue;
                }
                
                // If the cell above has an 'X', it's part of a vertical ship we've already counted.
                if (i > 0 && board[i - 1][j] == 'X') {
                    continue;
                }
                
                // If the cell to the left has an 'X', it's part of a horizontal ship we've already counted.
                if (j > 0 && board[i][j - 1] == 'X') {
                    continue;
                }
                
                // If we reach here, this 'X' is the top-left corner of a new battleship.
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
1. Initialize a battleship counter `count` to 0.
2. Get the dimensions of the board, `m` rows and `n` columns.
3. Iterate through each cell `(i, j)` of the board.
4. If `board[i][j]` is an 'X', check if it's the "head" of a battleship.
5. A cell `(i, j)` is considered a head if:
   a. The cell above it, `(i-1, j)`, does not contain an 'X'. (This condition is trivially true if `i` is 0).
   b. The cell to its left, `(i, j-1)`, does not contain an 'X'. (This condition is trivially true if `j` is 0).
6. If both conditions are met, it means we have found the top-leftmost part of a new battleship, so we increment `count`.
7. If either condition is not met, it means the current 'X' is part of a ship whose head we have already found and counted, so we do nothing.
8. After iterating through all cells, return the final `count`.

# Solutions
### Java

```java
class Solution {
public
  int countBattleships(char[][] board) {
    int m = board.length, n = board[0].length;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == '.') {
          continue;
        }
        if (i > 0 && board[i - 1][j] == 'X') {
          continue;
        }
        if (j > 0 && board[i][j - 1] == 'X') {
          continue;
        }
        ++ans;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def countBattleships(self, board: List[List[str]]) -> int: m, n = len(board), len(board[0]) ans = 0 for i in range(m): for j in range(n): if board[i][j] == '.': continue if i > 0 and board[i - 1][j] == 'X': continue if j > 0 and board[i][j - 1] == 'X': continue ans += 1 return ans

```

### CPP

```cpp
class Solution { public: int countBattleships ( vector < vector < char >>& board ) { int m = board . size (), n = board [ 0 ]. size (); int ans = 0 ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( board [ i ][ j ] == '.' ) continue ; if ( i > 0 && board [ i - 1 ][ j ] == 'X' ) continue ; if ( j > 0 && board [ i ][ j - 1 ] == 'X' ) continue ; ++ ans ; } } return ans ; } };
```