Description
Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.
Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).
Examples:
Example 1:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2
Example 2:
Input: board = [["."]]
Output: 0Solution in Python
To solve this problem, we need to count the number of battleships on the board based on the given rules. A battleship is represented by one or more contiguous 'X' characters, either horizontally or vertically. No two battleships are adjacent. We can solve this efficiently without modifying the board or using extra space by scanning the board and counting only the “starting cells” of battleships.
Approach:
- Identify Starting Cells:
- A cell in the matrix (
board[i][j]) is the start of a battleship if:board[i][j] == 'X'.- It is not part of a continuation of a battleship:
- The cell above (
board[i-1][j]) is not'X'. - The cell to the left (
board[i][j-1]) is not'X'.
- The cell above (
- This ensures that each battleship is counted exactly once.
- A cell in the matrix (
- Iterate Over the Board:
- Loop through each cell in the matrix.
- For each
'X', check if it satisfies the conditions to be the start of a battleship.
- Count Battleships:
- Maintain a counter to keep track of the number of starting cells.
Python
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
# Get dimensions of the board
m, n = len(board), len(board[0])
count = 0
# Iterate through each cell in the board
for i in range(m):
for j in range(n):
# Check if the cell contains 'X'
if board[i][j] == 'X':
# Check if it's the start of a battleship
# Not continuing from the top and not continuing from the left
if (i == 0 or board[i-1][j] != 'X') and (j == 0 or board[i][j-1] != 'X'):
count += 1
return countExplanation of the Code:
- Board Dimensions:
mis the number of rows, andnis the number of columns in the matrix.
- Iterate Over Cells:
- We use nested loops to check each cell in the matrix.
- Check Starting Conditions:
- For a cell
board[i][j]to be considered a new battleship:- It must contain
'X'. - It must not have another
'X'directly above (i == 0 or board[i-1][j] != 'X'). - It must not have another
'X'directly to the left (j == 0 or board[i][j-1] != 'X').
- It must contain
- For a cell
- Count Battleships:
- Increment the counter whenever a starting cell is identified.
- Return the Count:
- After scanning the entire board, return the total count of battleships.
Solution in C++
C++
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
// Get the dimensions of the board
int m = board.size();
int n = board[0].size();
// Initialize the count of battleships
int count = 0;
// Traverse through each cell in the board
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// Check if the current cell contains a battleship ('X')
if (board[i][j] == 'X') {
// If the cell above (i-1) exists and is part of a battleship, skip this cell
if (i > 0 && board[i-1][j] == 'X') continue;
// If the cell to the left (j-1) exists and is part of a battleship, skip this cell
if (j > 0 && board[i][j-1] == 'X') continue;
// If neither condition above is true, this cell is the "head" of a new battleship
count++;
}
}
}
// Return the total number of battleships
return count;
}
};Solution in Javascript
JavaScript
var countBattleships = function(board) {
// Initialize the count of battleships
let count = 0;
// Get the dimensions of the board
const m = board.length;
const n = board[0].length;
// Iterate over each cell in the board
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// Skip empty cells
if (board[i][j] === '.') continue;
// If the current cell is 'X' and:
// - The cell above is not part of a battleship
// - The cell to the left is not part of a battleship
// Then this is the start of a new battleship
if ((i === 0 || board[i - 1][j] === '.') &&
(j === 0 || board[i][j - 1] === '.')) {
count++;
}
}
}
// Return the total number of battleships found
return count;
};Solution in Java
Java
class Solution {
public int countBattleships(char[][] board) {
// Initialize a counter to keep track of the number of battleships
int count = 0;
// Iterate through each cell in the board
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
// Skip empty cells
if (board[i][j] == '.') {
continue;
}
// Check if the current cell is the "start" of a battleship
// A cell is the "start" if:
// - It contains an 'X'
// - It is not part of a battleship already counted (i.e., not connected to a previous 'X' horizontally or vertically)
if (i > 0 && board[i - 1][j] == 'X') {
// Skip cells connected vertically to a previous 'X'
continue;
}
if (j > 0 && board[i][j - 1] == 'X') {
// Skip cells connected horizontally to a previous 'X'
continue;
}
// Increment the count as this is the start of a new battleship
count++;
}
}
// Return the total number of battleships
return count;
}
}