419. Battleships in a Board

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?

思路:(借鉴discuss的)由于battleship形状必为矩形的特性,每个battleship都有一个最左上角(top-left)的元素,统计整个图中处于最左上角'X'的个数即可.
最左上角元素的'X'有何特征?其左侧和上方的元素都为'.',换句话说,左侧或上方为'X'的肯定是battleship内的非最左上结点;此外为'.'的是battleship外部结点,根据这两条规则即可.

同理,统计"最左下","最右上"和"最右下"结点的思路也是可以的.

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(); // 行
        int n = board[0].size(); //列
        int count = 0; // 计数器
        for (int i = 0; i < m; i++) { // 遍历board
            for (int j = 0; j < n; j++) {
            // 根据上面总结的规则判断,不符合则跳过本节点
                if (board[i][j] == '.') continue;
                if (i > 0 && board[i-1][j] == 'X') continue;
                if (j > 0 && board[i][j-1] == 'X') continue;
                count++; // 符合,找到一个"最左上"结点
            }
        }
        return count;
    }
};