Battleships in a Board
Real-world version: Counting Vessels on the ChartThe statement here is our own: the same inputs, outputs and technique.
A chart is given as board, each cell holding '.' for open water or 'X' for part of a vessel.
Every vessel lies in a single straight line, either along one row or down one column, and occupies a run of neighbouring cells. No two vessels touch, so between any two of them there is at least one cell of open water.
Return how many vessels are on the chart.
Examples
Example 1
- Input
- board = [["X", ".", ".", "X"], [".", ".", ".", "X"], [".", ".", ".", "X"], ["X", "X", ".", "."]]
- Output
- 3
There is a single cell at the top left, a run of three down the last column, and a run of two along the bottom row, which is three vessels.
Example 2
- Input
- board = [["X", "X", "X"]]
- Output
- 1
The three cells form one vessel lying along the row, counted once at its left-hand end.
Example 3
- Input
- board = [[".", ".", "."], [".", ".", "."], [".", ".", "."]]
- Output
- 0
The chart is all open water.
Constraints
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- Every row of board has the same length
- board[i][j] is either '.' or 'X'
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def count_battleships(board: list[list[str]]) -> int:public int countBattleships(char[][] board)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's