419. Battleships in a Board
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).
Example 1:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]] Output: 2
Example 2:
Input: board = [["."]] Output: 0
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]
is either'.'
or'X'
.
Follow up: Could you do it in one-pass, using only O(1)
extra memory and without modifying the values board
?
Solutions
Solution 1: Direct Iteration
We can iterate through the matrix, find the top-left corner of each battleship, i.e., the position where the current position is X
and both the top and left are not X
, and increment the answer by one.
After the iteration ends, return the answer.
The time complexity is $O(m \times n)$, where $m$ and $n$ are the number of rows and columns of the matrix, respectively. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|