LeetCode Battleships in a Board 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) or Nx1 (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
...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?

---

这一题的题意有点难懂，要问一个面板上有多少个舰队，注意是舰队，而不是单个的战舰。比如第一个例子中，为什么有两个舰队呢，左上角单独的X是一个舰队，右边的一列是另一个舰队，所以一共有两个舰队。 题目还限制了舰队只可能是横向或者纵向排列的，而且两个舰队之间至少有一个空位.隔开。 因为题中说所有测试数据都是合法的，且两个舰队之间至少有一个空位.隔开，所以可以用深搜DFS找有多少个X连成的区域，就有多少个舰队。完整代码如下： [cpp] class Solution { public: void dfs(vector<vector<char>>& board, vector<vector<char>>& mark, int i, int j) { if (mark[i][j] == 1)return; if (board[i][j] == ‘.’)return; mark[i][j] = 1; if (i – 1 >= 0) { dfs(board, mark, i – 1, j); } if (i + 1 < board.size()) { dfs(board, mark, i + 1, j); } if (j – 1 >= 0) { dfs(board, mark, i, j – 1); } if (j + 1 < board[i].size()) { dfs(board, mark, i, j + 1); } } int countBattleships(vector<vector<char>>& board) { int ans = 0; vector<vector<char>> mark(board.size(), vector<char>(board[0].size(), 0)); for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (mark[i][j] == 0 && board[i][j] == ‘X’) { ++ans; dfs(board, mark, i, j); } } } return ans; } }; [/cpp] 本代码提交AC，用时3MS。 Follow up中提到能否只用O(1)空间，且one-pass，网上题解提到，一个合法舰队的起始点的左边和上边肯定是空位.，否则这个X就会和其左边或者上边的X组成一个更大的舰队。所以我们只需要找面板中其左边和上边是.的X的个数。完整代码如下： [cpp] class Solution2 { public: int countBattleships(vector<vector<char>>& board) { int ans = 0; for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (board[i][j] == ‘X’) { if ((i == 0 || board[i – 1][j] == ‘.’) && (j == 0 || board[i][j – 1] == ‘.’)) { ++ans; } } } } return ans; } }; [/cpp] 本代码提交AC，用时6MS。]]>