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:

...XXXXX...X

This 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.

考察的是深度优先遍历的使用

思路：

通过DFS遍历四个方向 

	(i - 1, j)
(i, j - 1)	(i, j)	(i, j + 1)
	(i + 1, j)

X的一堆区域（都是X）就是一个战舰，求一共有多少战舰。

为了防止重复访问，用visited数组标记下已访问的结点

解答：

#include 
    
     #include 
     
      using namespace std;class Solution {public:	void dfs(vector
      
       
        >& board, int i, int j)	{		visited[i][j] = true;		//left		if (i >= 0 && i < n && j - 1 >= 0 && j - 1 < m && !visited[i][j - 1] && board[i][j - 1] == 'X')		{			dfs(board, i, j - 1);		}		//right		if (i >= 0 && i < n && j + 1 >= 0 && j + 1 < m && !visited[i][j + 1] && board[i][j + 1] == 'X')		{			dfs(board, i, j + 1);		}		//top		if (i - 1 >= 0 && i - 1 < n && j >= 0 && j < m && !visited[i - 1][j] && board[i - 1][j] == 'X')		{			dfs(board, i - 1, j);		}		//bottom		if (i + 1 >= 0 && i + 1 < n && j >= 0 && j < m && !visited[i + 1][j] && board[i + 1][j] == 'X')		{			dfs(board, i + 1, j);		}	}	int countBattleships(vector
        
         
          >& board) { n = board.size(); m = board[0].size(); num = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { visited[i][j] = false; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (board[i][j] == 'X' && !visited[i][j]) { num++; dfs(board, i, j); } } } return num; }private: int n; int m; int num; bool visited[1000][1000];};int main(){ Solution s; vector
          
           
             >vec{ { 'X', '.', '.', 'X' }, { '.', '.', '.', 'X' }, { '.', '.', '.', 'X' } }; cout << s.countBattleships(vec); return 0;}