419. Battleships in a Board

1. 思路（代码优化了该思路）

• 初始化：
  count = 0
• 遍历二维数组：
  遇到'X'时判断当前块的上方和左方存在'X'与否
  如果不存在，count ++
• 遍历结束即可得到Battleships的数量

2. 代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int count = 0;          //Battleships的数量
        bool flag;      //当前的状态：true时表示正在遍历Battleships，false时表示正在遍历Slots
        int M = (int)board.size();
        int N = (int)board[0].size();
        
        //cout<<M<<" "<<N<<endl;
        for(int i = 0 ; i < M ; i++ ) {
            flag = false;
            for(int j = 0 ; j < N ; j++ ) {
                if(i == 0) {    //第一行没有上一行，无需检查已经从上方被遍历
                    if(board[i][j] == 'X' && flag == false) {   //找到新的Battleship，因此count+1，flag为true
                        count++;
                        flag = true;//进入新的Battleship
                    }
                    else if(board[i][j] == '.' && flag == true) //遍历完成Battleship，flag为false
                        flag = false;
                }
                else {  //除第一行以外的其他行，检查上方是否已被遍历
                    if(board[i][j] == 'X' && flag == false && board[i - 1][j] == '.') {   //找到新的Battleship，因此count+1，flag为true，此'X'上方没有Battleship
                        count++;
                        flag = true;//进入新的Battleship
                    }
                    else if(board[i][j] == '.' && flag == true) //遍历完成Battleship，flag为false
                        flag = false;
                }
            }
        }
        return count;
    }
};

int main(int argc, const char * argv[]) {
    
    vector<vector<char>> board ;
    board = {
        {'X','.','.','X'},
        {'.','.','.','X'},
        {'.','.','.','X'}};
    Solution s ;
    cout<<s.countBattleships(board)<<endl;
    
    return 0;
}