## Similar Problems

Similar Problems not available

# Battleships In A Board - Leetcode Solution

LeetCode: Battleships In A Board Leetcode Solution

Difficulty: Medium

Topics: matrix depth-first-search array

Problem:
You have a board with m rows and n columns, where each cell contains either a `0`

or a `1`

. Starting from coordinate `[0, 0]`

, you take one step at a time in one of the four directions (up, down, left or right) until you reach the boundary of the board or an edge cell. Count the number of battleships on the board. Battleships are defined as any contiguous `1`

s that are not vertically or horizontally adjacent (i.e., they must not be positioned adjacent to each other in any of the four directions).

Solution: The key to this problem is to iterate through the matrix and count the number of battleships you encounter.

Algorithm:

- Initialize a variable
`count`

to 0. - Loop through each cell in the matrix.
- If a cell contains a
`1`

, check if it is the first cell of a battleship by checking if the cell above it and the cell to its left contain a`0`

. - If it is the first cell of a battleship, increment the count.
- After iterating through the matrix, return the count.

Code:

```
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
count = 0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'X':
if (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.'):
count += 1
return count
```

Explanation:
The code first initializes a variable `count`

to 0. It then loops through each cell in the matrix using nested for-loops. If a cell contains a `1`

, the code checks if it is the first cell of a battleship by checking if the cell above it and the cell to its left contain a `0`

. If it is the first cell of a battleship, the count is incremented.

After iterating through the matrix, the function returns the count.

Time Complexity: The time complexity of this solution is O(n*m) where n is the number of columns and m is the number of rows in the matrix.

Space Complexity: The space complexity of this solution is O(1) since we are not using any additional data structures to solve the problem.

## Battleships In A Board Solution Code

`1`