345. Battleships in a Board
You are given an m x n grid board where each cell is either 'X' (part of a battleship) or '.' (water). Count how many battleships the board contains.
Every battleship is a straight line of 'X' cells exactly one cell wide — it occupies a 1 x k horizontal strip or a k x 1 vertical strip (k >= 1). The board is always well-formed: two different ships never touch horizontally or vertically; at least one cell of water separates them (diagonal contact can occur and is fine).
Return the number of battleships as an integer. Can you do it in one pass over the grid, without extra memory and without modifying the board?
Example 1:
Input: board = ["X..X", "...X", "...X"]
Output: 2
Explanation: The lone 'X' at (0, 0) is a 1-cell ship, and the three 'X' cells down the last column form one vertical ship.
Example 2:
Input: board = ["X.", ".X"]
Output: 2
Explanation: The two 'X' cells touch only diagonally, which the rules allow — they are two separate 1-cell ships.
Constraints:
- 1 ≤ m, n ≤ 200
- board[r][c] is 'X' or '.'
- Ships are 1 x k or k x 1 straight strips, and distinct ships never share a horizontal or vertical border.
Hints:
Connected-component counting (flood fill from every unvisited 'X') works, but it ignores the strong guarantees the board gives you.
Because ships are straight strips that never touch, each ship has exactly one top-left-most cell — its head. Counting ships is the same as counting heads.
A cell is a head exactly when it is 'X', the cell above is not 'X', and the cell to the left is not 'X'. That test needs no visited array and no mutation.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = ["X..X", "...X", "...X"]
Expected output: 2