Solution Explanation: Counting Battleships in a Board

The problem asks to count the number of battleships in a given board represented as a matrix of characters. Battleships are represented by 'X' and empty cells by '.'. Battleships can be placed horizontally or vertically, but never diagonally, and they cannot touch each other (horizontally or vertically).

The most efficient approach is a single pass through the board, avoiding unnecessary recursion or complex data structures. The core idea is to identify only the top-leftmost cell of each battleship.

Algorithm:

1. Initialization: Initialize a counter ans to 0. This will store the count of battleships.
2. Iteration: Iterate through each cell of the board using nested loops.
3. Battleship Check: For each cell containing 'X', check the following conditions:
   • Check above: If the cell above (i-1, j) is also 'X', it means this 'X' is part of a battleship already counted. Skip this cell.
   • Check left: If the cell to the left (i, j-1) is also 'X', it means this 'X' is part of a battleship already counted. Skip this cell.
4. Increment Counter: If neither of the above conditions is met, it means this 'X' is the top-leftmost cell of a new battleship. Increment ans.
5. Return Count: After iterating through the entire board, return ans.

Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the board. We visit each cell exactly once.

Space Complexity: O(1). We use a constant amount of extra space to store the counter ans. No additional data structures are needed.

Code Implementation (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] == 'X':  #Check if it's a battleship cell
                    if (i > 0 and board[i - 1][j] == 'X') or \
                       (j > 0 and board[i][j - 1] == 'X'):
                        continue  #Skip if part of an already counted battleship
                    ans += 1  #Increment count for a new battleship
        return ans

Code Implementation (Java):

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length;
        int 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] == 'X') {
                    if ((i > 0 && board[i - 1][j] == 'X') ||
                            (j > 0 && board[i][j - 1] == 'X')) {
                        continue;
                    }
                    ans++;
                }
            }
        }
        return ans;
    }
}

Code Implementation (JavaScript):

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function(board) {
    let count = 0;
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] === 'X') {
                if ((i > 0 && board[i-1][j] === 'X') || (j > 0 && board[i][j-1] === 'X')) continue;
                count++;
            }
        }
    }
    return count;
};
 

The code in other languages (C++, Go, TypeScript) would follow a very similar structure, adapting syntax as needed. The core logic remains the same.