Given an 2D board, count how many 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 ...XIn the above board there are 2 battleships.
Invalid Example:
...X XXXX ...XThis 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?
思路：
首先想到dfs。
void dfsbattle(vector<vector<char>>& board,vector<vector<bool>>& visited,int i,int j) { int m = board.size(), n = board[0].size(); if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] == ‘.‘)return; visited[i][j] = true; dfsbattle(board, visited, i + 1, j); dfsbattle(board, visited, i - 1, j); dfsbattle(board, visited, i , j+1); dfsbattle(board, visited, i , j-1); } int countBattleships(vector<vector<char>>& board) { if (board.empty())return 0; int m = board.size(), n = board[0].size(); vector<vector<bool>>visited(m, vector<bool>(n, false)); int ret = 0; for (int i = 0; i < m;i++) { for (int j = 0; j < n;j++) { if (board[i][j]==‘X‘&& !visited[i][j]) { dfsbattle(board, visited, i,j); ret++; } } } return ret; }
又题目提到不用额外空间，而且只遍历一次。。
public int countBattleships(char[][] board) { int count = 0; for(int i=0;i<board.length;i++) for(int j=0;j<board[0].length;j++) if(board[i][j]==‘X‘ && (i==0 || board[i-1][j]!=‘X‘) && (j==0 || board[i][j-1]!=‘X‘)) count++; return count; }
参考：
https://discuss.leetcode.com/topic/64027/share-my-7-line-code-1-line-core-code-3ms-super-easy
[leetcode-419-Battleships in a Board]
原文：http://www.cnblogs.com/hellowooorld/p/7152990.html