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:
1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.Example:
X..X ...X ...X
In the above board there are 2 battleships.
Invalid Example:
...X XXXX ...X
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
FOLLOW UP
//little tricky way only care about the left and up case public int countBattleships(char[][] board) { if(board == null || board.length == 0) return 0; int row = board.length; int col = board[0].length; int res = 0; for(int i = 0; i < row ; i++){ for(int j = 0; j < col ; j++){ if(board[i][j] == ‘X‘){ if(i > 0 && board[i-1][j] == ‘X‘) continue; if(j > 0 && board[i][j-1] == ‘X‘) continue; res++; } } } return res; }
DFS
public class Solution { public int countBattleships(char[][] board) { if(board == null || board.length == 0) return 0; int row = board.length; int col = board[0].length; int res = 0; for(int i = 0; i < row ; i++){ for(int j = 0; j < col ; j++){ if(board[i][j] == ‘X‘){ dfs(board , i, j); res++; } } } return res; } public void dfs(char[][] board, int i, int j){ if(i < 0 || i >= board.length || j < 0 || j >=board[0].length || board[i][j] == ‘.‘){ return; } board[i][j] = ‘.‘; dfs(board , i+1, j); dfs(board , i, j+1); dfs(board , i-1, j); dfs(board , i, j-1); } }
原文：http://www.cnblogs.com/joannacode/p/6108135.html