Count the Ships on a Valid Battleship Board

# Count the Ships on a Valid Battleship Board A rectangular `board` contains `'X'` for ship cells and `'.'` for empty cells. Return the number of ships. Every ship is one straight horizontal or vertical segment: either `1` by `k` or `k` by `1` cells for some positive `k`. Different ships never touch along an edge; at least one empty cell separates them horizontally or vertically. ### Function `int countBattleships(vector<vector<char>>& board)` ### Example 1 ```text Input: board = [["X","X",".","X"],[".",".",".","X"],["X",".",".","X"]] Output: 3 ``` There is a two-cell horizontal ship, a three-cell vertical ship in the last column, and a single-cell ship at the bottom-left. ### Example 2 ```text Input: board = [["X"]] Output: 1 ``` ### Constraints - `m == board.length` and `n == board[i].length`. - `1 <= m,n <= 200`. - Every cell is `'X'` or `'.'`. - The board follows the stated straight-ship and separation rules. ### Clarifications Count ships, not occupied cells. A one-cell ship is valid. This task assumes a valid board; detecting bends or invalid touching ships is not required. ### What a Strong Answer Covers - Horizontal, vertical, and single-cell ships. - An empty-of-ships board and ships at grid boundaries. - Why every ship is counted exactly once. - Correctness and resource bounds. ### Follow-up Questions Can you use one pass and `O(1)` extra memory without modifying the board?