Approach: Count ship heads

count each 'X' whose top and left neighbours are not 'X' — that cell is the head of a distinct ship

Complexity: O(m*n) time, O(1) space.

Full Solution — all languages

class Solution:
    def countBattleships(self, grid):
        R, C = len(grid), len(grid[0])
        cnt = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'X' and (r == 0 or grid[r-1][c] != 'X') and (c == 0 or grid[r][c-1] != 'X'):
                    cnt += 1
        return cnt

import java.util.*;
class Solution {
    public int countBattleships(char[][] grid) {
        int R = grid.length, C = grid[0].length, cnt = 0;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 'X' && (r == 0 || grid[r-1][c] != 'X') && (c == 0 || grid[r][c-1] != 'X')) cnt++;
        return cnt;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int countBattleships(vector<vector<char>>& grid) {
        int R = grid.size(), C = grid[0].size(), cnt = 0;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 'X' && (r == 0 || grid[r-1][c] != 'X') && (c == 0 || grid[r][c-1] != 'X')) cnt++;
        return cnt;
    }
};

/**
 * @param {character[][]} grid
 * @return {number}
 */ var countBattleships = function(grid) {
    const R = grid.length, C = grid[0].length;
    let cnt = 0;
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 'X' && (r === 0 || grid[r-1][c] !== 'X') && (c === 0 || grid[r][c-1] !== 'X')) cnt++;
    return cnt;
};

Battleships in a Board

Example 1

Example 2

Constraints