Given an 2D board, count how many different battleships are in it. The battleships are represented with
'X'
s, empty slots are represented with '.'
s. You may assume the following rules:- You receive a valid board, made of only battleships or empty slots.
- Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape
1xN
(1 row, N columns) orNx1
(N rows, 1 column), where N can be of any size. - At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X ...X ...XIn the above board there are 2 battleships.
Invalid Example:
...X XXXX ...XThis is not a valid board - as battleships will always have a cell separating between them.
Your algorithm should not modify the value of the board.
Analysis:
At the very first glance, it looks like a BFS/DFS to find the group of connected nodes. But it has the limit that all the battleships have to be in the same row or column. In addition, it has the limit that the board cannot be changed, which means you cannot mark the board as visited or not.
Given that the battleship must be in the same row or column, we can simply check all rows and columns and count it if it is a valid battleship. For each row, we need to collect the number of battleships, which is nothing but the same as finding the number of word separated by space. Notice that you need to check whether the battleship is valid or not by checking whether it has upper or down row battleship connected. Similarly we can get the battleships for the columns, except that for the battleship occupying only one space which has been collected by the row already, so no need to recollected.
Comparing to other solutions, this solution is able to take care of the invalid board as well.
Given that the battleship must be in the same row or column, we can simply check all rows and columns and count it if it is a valid battleship. For each row, we need to collect the number of battleships, which is nothing but the same as finding the number of word separated by space. Notice that you need to check whether the battleship is valid or not by checking whether it has upper or down row battleship connected. Similarly we can get the battleships for the columns, except that for the battleship occupying only one space which has been collected by the row already, so no need to recollected.
Comparing to other solutions, this solution is able to take care of the invalid board as well.
int getColCount(char[][] board, int k) {
int m = board.length;
int n = board[0].length;
int i = 0;
int count = 0;
while(i < m) {
while(i < m && board[i][k] == '.')
i++;
boolean valid = true;
int c = 0;
while(i < m && board[i][k] == 'X') {
if ((k > 0 && board[i][k-1] == 'X') || (k < n-1 && board[i][k+1] == 'X'))
valid = false;
i++;
c++;
}
//exclude the single node
if (valid && c > 1)
count++;
}
return count;
}
int getRowCount(char[][] board, int k) {
int m = board.length;
int n = board[0].length;
int i = 0;
int count = 0;
while(i < n) {
while(i <n && board[k][i] == '.')
i++;
boolean valid = true;
int c = 0;
while(i <n && board[k][i] == 'X') {
if ((k > 0 && board[k-1][i] == 'X') || (k < m-1 && board[k+1][i] == 'X'))
valid = false;
i++;
c++;
}
if (valid && c > 0)
count++;
}
return count;
}
public int countBattleships(char[][] board) {
int count = 0;
if (board.length == 0)
return 0;
for(int i=0; i<board.length; i++)
count+= getRowCount(board, i);
for(int i=0; i<board[0].length; i++)
count+= getColCount(board, i);
return count;
}
No comments:
Post a Comment