Question

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:

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?

---

Solution

一个valid board 中，只有两种类型的元素：‘X’ 或者 ‘.’ 。X是战舰的组成部分，且战舰只能水平或者垂直放置。所以对于一个X元素，其上、下、左、右的4个相邻的位置存在X元素时，这两个X属于同一艘战舰。依次递归，可以找出所有同属于一艘战舰的X元素。

解法一：

要统计战舰的数量，则可以遍历board中的每一个位置，遇到“未访问过的”X元素时，认为找到了一艘战舰，此时战舰数量增加1。同时，需要将这艘战舰的其他的X元素，置为“已访问过”。即对其上、下、左、右，四个相邻的位置进行深度优先遍历。 需要维护一个二位数组，存储每个位置是否已经访问过的标志。

解法二：

由于战舰必须水平或者垂直放置。所以每一艘战舰，要不存在一个最左边的X元素（水平放置时），要不存在一个最上边X元素（垂直放置时）。 即共有4中类型的X元素： 1）水平放置时，最左边的X元素。（其上、左、下三个位置都为‘.’） 2）水平放置时，其他的X元素。（其左一定是X） 3）垂直放置时，最上面的X元素。（其上、左、右三个位置都为‘.’） 4）垂直放置时，其他的X元素。（其上一定是X） 通过X元素上、左两个位置的值，可以区分出这4个类型。

只需要统计1、3两种X元素的个数，就可以得到战舰的个数。遍历board上的每一个位置，遍历每一个X元素，如果X元素的左边为X，则不需要统计，如果X元素的上面为X，则不需要统计；否则，战舰数增加1。