Battleships in a Board
Medium · Matrix · Array · Matrix · Depth-First Search
Problem
An m x n board has cells that are either 'X' (part of a battleship) or '.' (open water). Every battleship is a straight line of cells, one cell wide: 1 x k across or k x 1 down. No two ships touch side by side: at least one open cell separates them horizontally and vertically (they may meet at a corner).
Return the number of battleships on the board.
Can you do it in one pass, with O(1) extra memory and without changing the board?
Examples
Input: board = [["X",".","X"],[".",".","X"],["X",".","."]] Output: 3
A one-cell ship at the top left, a ship running down the last column, and a one-cell ship at the bottom left.
Input: board = [["X","X","X"]] Output: 1
The whole row is one ship.
Constraints
- m == len(board), n == len(board[i])
- 1 <= m, n <= 200
- board[i][j] is '.' or 'X'
- Ships are straight lines and never touch side by side
Approaches
- Flood fill each ship — time O(m · n), space O(m · n)
Follow-up
What if ships could bend (any connected group of cells)? A group can then have several cells with nothing above or to the left, so the head count breaks; you are back to flood fill or union-find over the grid.
Related problems
Start free on Cariara · Coding problems · System design studio
