leetcode 419. Battleships in a Board

约定不等于承诺〃 2022-06-13 02:59 96阅读 0赞

# 1.题目 #

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.  
给一个二维数组表示甲板，N个’X连在一起表示军舰，军舰只会横向或纵向摆放，1xN (1 row, N columns) or Nx1 (N rows, 1 column)，N为任意大小。’.’表示空。军舰与军舰之间不相邻，必须有空。  
Example:  
X..X  
…X  
…X  
上面有两个军舰  
Invalid Example:不合法的例子  
…X  
XXXX  
…X  
上面的军舰没有空隙，不合法。我们假设所有的输入都是合法的。  
Follow up:  
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

# 2.分析 #

看了solution，自己一开始实在想不到怎么数。

只要找到每个军舰的第一个’X’。因为军舰之间是有空隙的，所以第一个’X’的左边和上边一定不是’X’。

# 3.代码 #

class Solution {
    public:
        int countBattleships(vector<vector<char>>& board) {
            int count = 0;
            for (int i = 0; i < board.size(); i++) 
                for (int j = 0; j < board[0].size(); j++) 
                    if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X'))
                        ++count;
            return count;
        }
    };