Battleships in a board

111.Count Battleships

Matrix

Simulation

Problem Statement:

Given a 2D board representing a battleship grid, count the number of distinct battleships on the board. The board is filled with 'X' and '.'. Battleships can only be placed horizontally or vertically, and there must be at least one cell gap ('.') between any two battleships.

Algorithm:

1. Traverse the grid cell by cell.
2. For each cell containing 'X':
   • Check if the cell above or to the left contains 'X'.
   • If either condition is true, skip the current cell since it belongs to an already counted battleship.
   • If neither condition is true, increment the battleship count.
3. Continue until all cells are processed and return the total count.

Complexity:

Time: O(m × n), where m is the number of rows and n is the number of columns | Space: O(1).

Java Implementation:

// In-place solution, check only previous cells
public int countBattleships(char[][] board) {
    int m = board.length;
    if (m == 0) return 0;
    int n = board[0].length;

    int count = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == '.') continue; // Skip empty cells
            if (i > 0 && board[i - 1][j] == 'X') continue; // Skip if part of vertical battleship
            if (j > 0 && board[i][j - 1] == 'X') continue; // Skip if part of horizontal battleship
            count++; // Count distinct battleship
        }
    }

    return count;
}
                

Python Implementation:

def countBattleships(board):
    if not board or not board[0]:
        return 0

    m, n = len(board), len(board[0])
    count = 0

    for i in range(m):
        for j in range(n):
            if board[i][j] == '.':
                continue
            if i > 0 and board[i - 1][j] == 'X':
                continue
            if j > 0 and board[i][j - 1] == 'X':
                continue
            count += 1

    return count
                

C++ Implementation:

int countBattleships(vector>& board) {
    if (board.empty() || board[0].empty()) return 0;

    int m = board.size();
    int n = board[0].size();
    int count = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == '.') continue; // Skip empty cells
            if (i > 0 && board[i - 1][j] == 'X') continue; // Skip if part of vertical battleship
            if (j > 0 && board[i][j - 1] == 'X') continue; // Skip if part of horizontal battleship
            count++; // Count distinct battleship
        }
    }

    return count;
}