419. Battleships in a Board

Link: https://leetcode.com/problems/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?

---

題目翻譯:

給定 2D 板，計算其中有多少戰列艦。戰列艦用’X’表示，空位用’。’表示。您可以遵守以下規則：

• 您收到一個有效的板，僅由戰艦或空槽組成。
• Battleships 只能水平放置或垂直放置。換句話說，它們只能由 1xN（1 行，N 列）或 Nx1（N 行，1 列）的形狀組成，其中 N 可以是任何大小。
• 至少有一個水平或垂直的單元格在兩艘戰列艦之間分開 - 沒有相鄰的戰列艦。

程式思路:
遇到’X’時檢查它的上方跟左方是不是’X’，如果都不是表示這個點就是船頭。

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int result = 0;
        auto IsExtandofBoard = [&](int x ,int y)
        {
            if(0 <= x && x < board.size() && 0 <= y && y < board[0].size() && board[x][y] == 'X')
            {
                   return true;
            }
            return false;
        };
        for(int i = 0;i < board.size();i++)
        {
             for(int j = 0;j < board[0].size();j++)
             {
                 if(board[i][j] == 'X')
                 {
                    if(!IsExtandofBoard(i,j-1) && !IsExtandofBoard(i-1,j)) // left & up
                      result++;
                 }
             }
        }
        return result;
    }
};