grid47 Exploring patterns and algorithms
Sep 26, 2024
6 min read
Solution to LeetCode 419: Battleships in a Board Problem
You are given a grid representing a battleship field, where ‘X’ marks the location of a part of a battleship and ‘.’ represents an empty sea cell. A battleship is either placed horizontally or vertically on the grid, with no adjacent battleships (there must be at least one empty cell between any two battleships). Your task is to count the number of distinct battleships on the grid.
Problem
Approach
Steps
Complexity
Input: The input is a 2D character grid where each cell contains either 'X' (part of a battleship) or '.' (empty sea).
• Explanation: In this case, there are two distinct battleships. The first one is placed horizontally from (0,0) to (0,3), and the second one is placed vertically from (0,3) to (2,3). Thus, the output is 2.
Approach: To solve this problem efficiently, iterate through each cell of the grid. For each 'X', check if it is the start of a new battleship by ensuring there are no other 'X' directly above or to the left of it. If it is, increment the battleship count.
Observations:
• We need to avoid counting the same battleship multiple times.
• Each battleship can only be counted once, either from the start of the row or the start of the column.
• By checking the adjacent cells (above and to the left), we can avoid double-counting parts of the same battleship.
Steps:
• Initialize a counter to track the number of battleships.
• Iterate through the grid, cell by cell.
• For each 'X', check if it is not adjacent to another 'X' from above or to the left.
• If it is not, count it as the start of a new battleship.
Empty Inputs:
• If the board is empty (no rows or columns), the output should be 0.
Large Inputs:
• For large grids (up to 200x200), ensure the solution can handle the maximum input size efficiently.
Special Values:
• A grid where all cells are empty should return 0, as there are no battleships.
Constraints:
• The solution should work within the problem's constraints, with a maximum grid size of 200x200.
intcountBattleships(vector<vector<char>>& board) {
if(board.empty() || board[0].empty()) return0;
int m = board.size(), n = board[0].size();
int cnt =0;
for(int i =0; i < m; i++)
for(int j =0; j < n; j++) {
cnt += (board[i][j] =='X') && (i ==0|| board[i -1][j] !='X') && (j ==0|| board[i][j -1] !='X');
}
return cnt;
}
This line declares the `countBattleships` function, which takes a 2D vector of characters representing the board and returns an integer representing the number of battleships.
2 : Edge Case Handling
if(board.empty() || board[0].empty()) return0;
This checks if the board is empty or if the first row is empty. If either condition is true, it returns 0 as there are no battleships to count.
3 : Variable Initialization
int m = board.size(), n = board[0].size();
Here, we initialize the variables `m` and `n` to represent the number of rows and columns in the board.
4 : Variable Initialization
int cnt =0;
This initializes the `cnt` variable to keep track of the number of battleships found on the board.
5 : Loop Initialization
for(int i =0; i < m; i++)
This starts a loop to iterate over each row of the board.
6 : Loop Initialization
for(int j =0; j < n; j++) {
This starts a nested loop to iterate over each column within the current row.
This line checks if the current cell is an 'X' (part of a battleship). It also ensures that the current cell is not part of a battleship that has already been counted (i.e., no adjacent 'X' cells to the left or above). If both conditions are true, it increments the `cnt` variable.
8 : Return Statement
return cnt;
This returns the final count of battleships found on the board.
Best Case: O(m * n), where m is the number of rows and n is the number of columns in the grid.
Average Case: O(m * n), as we must inspect every cell in the grid.
Worst Case: O(m * n), since we iterate through the entire grid once.
Description: The time complexity is linear with respect to the size of the grid.
Best Case: O(1), since no additional space is required besides the input grid.
Worst Case: O(1), as the solution uses only a constant amount of extra memory.
Description: The space complexity is constant because we do not use any extra data structures that depend on the size of the grid.
