นับเรือรบในกระดาน (Battleships in a Board) ใน C++

นับเรือรบในกระดาน (Battleships in a Board)

ให้กระดาน 2D ที่มี 'X' แทนเรือรบ และ '.' แทนช่องว่าง เรือรบเป็นรูป 1xN หรือ Nx1 (แนวนอนหรือแนวตั้ง) และมีช่องว่างอย่างน้อย 1 ช่องคั่นระหว่างเรือ นับจำนวนเรือรบ

ตัวอย่าง: X . . X . . . X . . . X → 2 เรือ (ตัวแนวตั้งขนาด 3 และตัวแนวนอนขนาด 1)

ขั้นตอนการแก้ปัญหา (One-pass, O(1) Space)

ans = 0
วนทุกเซลล์ (i, j):
- ถ้า board[i][j] == '.' ข้าม
- ถ้า i > 0 && board[i-1][j] == 'X' ข้าม (เป็นส่วนต่อเนื่องของเรือแนวตั้ง)
- ถ้า j > 0 && board[i][j-1] == 'X' ข้าม (เป็นส่วนต่อเนื่องของเรือแนวนอน)
- มิฉะนั้นเป็นหัวเรือใหม่ ans++
คืนค่า ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

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

อินพุทและเอาต์พุทตัวอย่าง

Input: [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]

Output: 2