Battleships

108.Battleships in a Board

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 each cell of the board.
2. For each cell containing 'X':
   • If the cell above or to the left is also 'X', skip the cell since it belongs to an already counted battleship.
   • Otherwise, increment the battleship count.
3. Return the total count of battleships.

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;
}