Battleships in a Board

medium array dfs matrix

Problem

Given an m x n board where 'X' represents ship cells and '.' empty water, return the number of battleships. Battleships occupy a single row or column with at least one cell between any two ships.

Inputboard = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]

Output2

A horizontal ship in the top-left corner and a vertical ship in the right column.

board (rows separated by ; cells comma-separated)

def count_battleships(board):
    count = 0
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] != 'X':
                continue
            if r > 0 and board[r-1][c] == 'X':
                continue
            if c > 0 and board[r][c-1] == 'X':
                continue
            count += 1
    return count

function countBattleships(board) {
  let count = 0;
  for (let r = 0; r < board.length; r++) {
    for (let c = 0; c < board[0].length; c++) {
      if (board[r][c] !== 'X') continue;
      if (r > 0 && board[r-1][c] === 'X') continue;
      if (c > 0 && board[r][c-1] === 'X') continue;
      count++;
    }
  }
  return count;
}

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (board[r][c] != 'X') continue;
                if (r > 0 && board[r-1][c] == 'X') continue;
                if (c > 0 && board[r][c-1] == 'X') continue;
                count++;
            }
        }
        return count;
    }
}

int countBattleships(vector<vector<char>>& board) {
    int count = 0;
    for (int r = 0; r < (int)board.size(); r++) {
        for (int c = 0; c < (int)board[0].size(); c++) {
            if (board[r][c] != 'X') continue;
            if (r > 0 && board[r-1][c] == 'X') continue;
            if (c > 0 && board[r][c-1] == 'X') continue;
            count++;
        }
    }
    return count;
}

Explanation

Each battleship is a straight line of 'X' cells, and ships never touch. The neat trick is that we don't need to trace whole ships — we just count each ship's top-left corner, which appears exactly once per ship.

A cell is a top-left corner when it is an 'X' but the cell above it and the cell to its left are not 'X' (either water or off the board). Every other 'X' in a ship has a ship cell directly above or to the left, so it gets skipped.

So we scan the whole board once and add 1 to count only when both checks pass. No extra visited array or recursion is needed, which is why this runs in constant extra space.

Example: in [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]], the top-left X has nothing above or left, so it counts. The right column's top X also counts, but the two Xs below it have a ship above, so they are skipped — total 2.

Time: O(m·n) Space: O(1)