Battleships In A Board

                                            
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int count = 0;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                    count++;
                }
            }
        }
        return count;
    }
};

                                            
class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

                                            
class Solution(object):
    def countBattleships(self, board):
        count = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X':
                    if i > 0 and board[i - 1][j] == 'X':
                        continue
                    if j > 0 and board[i][j - 1] == 'X':
                        continue
                    count += 1
        return count

                                            
int countBattleships(char** board, int boardSize, int* boardColSize) {
    int count = 0;
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < *boardColSize; j++) {
            if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X')) {
                count++;
            }
        }
    }
    return count;
}

                                            
public class Solution {
    public int CountBattleships(char[][] board) {
        int count = 0;
        for (int i = 0; i < board.Length; i++) {
            for (int j = 0; j < board[i].Length; j++) {
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                    count++;
                }
            }
        }
        return count;
    }
}

                                            
/**
 * @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[i].length; j++) {
            if (board[i][j] === 'X' && (i === 0 || board[i-1][j] === '.') && (j === 0 || board[i][j-1] === '.')) {
                count++;
            }
        }
    }
    return count;
};

                                            
function countBattleships(board: string[][]): number {
    let count = 0;
    
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (board[i][j] === 'X' && (i === 0 || board[i - 1][j] !== 'X') && (j === 0 || board[i][j - 1] !== 'X')) {
                count++;
            }
        }
    }
    
    return count;
};

                                            
class Solution {
    /**
     * @param String[][] $board
     */
    function countBattleships($board) {
        $count = 0;
        for ($i = 0; $i < count($board); $i++) {
            for ($j = 0; $j < count($board[$i]); $j++) {
                if ($board[$i][$j] == 'X' && ($i == 0 || $board[$i-1][$j] == '.') && ($j == 0 || $board[$i][$j-1] == '.')) {
                    $count++;
                }
            }
        }
        return $count;
    }
}

                                            
class Solution {
    func countBattleships(_ board: [[Character]]) -> Int {
        var count = 0
        for i in 0..<board.count {
            for j in 0..<board[i].count {
                if board[i][j] == "X" {
                    if (i == 0 || board[i - 1][j] != "X") && (j == 0 || board[i][j - 1] != "X") {
                        count += 1
                    }
                }
            }
        }
        return count
    }
}

                                            
class Solution {
    fun countBattleships(board: Array<CharArray>): Int {
        var count = 0
        for (i in board.indices) {
            for (j in board[i].indices) {
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X')) {
                    count++
                }
            }
        }
        return count
    }
}

                                            
class Solution {
  int countBattleships(List<List<String>> board) {
      int count = 0;
      
      for (int i = 0; i < board.length; i++) {
          for (int j = 0; j < board[i].length; j++) {
              if (board[i][j] == 'X') {
                  if ((i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X')) {
                      count++;
                  }
              }
          }
      }
      
      return count;
  }
}

                                            
func countBattleships(board [][]byte) int {
    count := 0
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[i]); j++ {
            if board[i][j] == 'X' {
                if (i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.') {
                    count++
                }
            }
        }
    }
    return count
}

                                            
# @param {Character[][]} board
# @return {Integer}
def count_battleships(board)
    count = 0
    (0...board.length).each do |i|
        (0...board[0].length).each do |j|
            if board[i][j] == 'X' && (i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.')
                count += 1
            end
        end
    end
    count
end

                                            
object Solution {
    def countBattleships(board: Array[Array[Char]]): Int = {
        var count = 0
        for (i <- 0 until board.length; j <- 0 until board(0).length) {
            if (board(i)(j) == 'X' && (i == 0 || board(i - 1)(j) == '.') && (j == 0 || board(i)(j - 1) == '.')) {
                count += 1
            }
        }
        count
    }
}

                                            
impl Solution {
    pub fn count_battleships(board: Vec<Vec<char>>) -> i32 {
        let mut count = 0;
        
        for i in 0..board.len() {
            for j in 0..board[i].len() {
                if board[i][j] == 'X' &&
                    (i == 0 || board[i - 1][j] == '.') &&
                    (j == 0 || board[i][j - 1] == '.') {
                    count += 1;
                }
            }
        }
        
        count
    }
}

To solve this coding challenge, the goal is to count the number of distinct battleships on a given m x n board without modifying the board and using O(1) extra memory. A battleship is represented by a series of contiguous 'X' cells that are either aligned horizontally or vertically, and no two battleships are adjacent to each other. This means that between any two battleships, there should be at least one '.' cell.

Explanation

The primary trick is to traverse the board and identify the starting cell of each battleship. A cell is considered the starting cell of a battleship if:

It contains an 'X'.
The cell above it (if it exists) does not contain an 'X'.
The cell to the left of it (if it exists) does not contain an 'X'.

By ensuring these conditions, each 'X' will only be counted once per battleship, effectively eliminating any redundancy in counting.

Detailed Steps in Pseudocode

Initialize a counter variable to zero.
Iterate over each row of the board.
Within each row, iterate over each cell.
For each cell that contains an 'X':

Check if it is the starting cell of a battleship (i.e., ensure that neither the cell above it nor the cell to the left of it has an 'X').
If it is the starting cell, increment the counter.

Return the counter as the result.

Pseudocode

                                            
# Initialize a function to count battleships on the board
function countBattleships(board):
    # Initialize a counter for battleships
    battleship_count = 0
    
    # Iterate through each row index in the board
    for row_index in range(0, length(board)):
        # Iterate through each column index in the board
        for col_index in range(0, length(board[row_index])):
            # Check if the current cell contains an 'X'
            if board[row_index][col_index] == 'X':
                # Check if there is a cell above the current cell and if that cell contains an 'X'
                if row_index > 0 and board[row_index - 1][col_index] == 'X':
                    # If true, it means this 'X' is part of a vertically continuing battleship, so continue to the next iteration
                    continue
                
                # Check if there is a cell to the left of the current cell and if that cell contains an 'X'
                if col_index > 0 and board[row_index][col_index - 1] == 'X':
                    # If true, it means this 'X' is part of a horizontally continuing battleship, so continue to the next iteration
                    continue
                
                # If the current 'X' is the starting point of a battleship, increment the battleship counter
                battleship_count += 1
    
    # Return the total count of battleships
    return battleship_count

This pseudocode ensures that we scan the board in one pass, using only O(1) extra memory for the counter and a few variables for indexing and condition checking. This adheres to the constraints provided and meets the requirements of the challenge efficiently.