_419. Battleships in a Board.md

419. Battleships in a Board

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 24, 2024

Last updated : June 24, 2024

---

Related Topics : Array, Depth-First Search, Matrix

Acceptance Rate : 76.25 %

---

Solutions

• m419 v2 O(1) Space One Pass O(n).py
• m419 v2.c
• m419.c

Python

m419 v2 O(1) Space One Pass O(n).py

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        counter = 0

        # find corners
        for r in range(len(board)) :
            for c in range(len(board[0])) :
                if board[r][c] == 'X' \
                    and (c == 0 or board[r][c - 1] == '.') \
                    and (r == 0 or board[r - 1][c] == '.'):
                    counter += 1

        return counter

C

m419 v2.c

int countBattleships(char** board, int boardSize, int* boardColSize) {
    int counter = 0;

    for (int r = 0; r < boardSize; r++) {
        for (int c = 0; c < boardColSize[0]; c++) {
            if (board[r][c] == 'X'
                && (c == 0 || board[r][c - 1] == '.')
                && (r == 0 || board[r - 1][c] == '.'))
                counter++;
        }
    }
    return counter;
}

m419.c

void removeShip(char** board, int boardSize, int* boardColSize, int x, int y) {
    if (x < 0 || x >= boardSize || y < 0 || y >= boardColSize[0] || board[x][y] == '.') {
        return;
    }

    board[x][y] = '.';

    removeShip(board, boardSize, boardColSize, x + 1, y);
    removeShip(board, boardSize, boardColSize, x - 1, y);
    removeShip(board, boardSize, boardColSize, x, y + 1);
    removeShip(board, boardSize, boardColSize, x, y - 1);
}

int countBattleships(char** board, int boardSize, int* boardColSize) {
    int counter = 0;

    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[0]; j++) {
            if (board[i][j] == 'X') {
                counter++;
                removeShip(board, boardSize, boardColSize, i, j);
            }
        }
    }
    return counter;
}