मान लीजिए हमारे पास एक 2D बोर्ड है। हमें गिनना है कि इसमें कितने युद्धपोत (battleships) हैं। युद्धपोत 'X' से दर्शाए जाते हैं, खाली स्लॉट '.' से। नियम:
- वैध बोर्ड: केवल युद्धपोत या खाली स्लॉट।
- युद्धपोत केवल क्षैतिज (1xN) या लंबवत (Nx1) रखे जा सकते हैं।
- दो युद्धपोतों के बीच कम से कम एक क्षैतिज या लंबवत सेल का अंतर होता है।
उदाहरण:
X . . X . . . X . . . Xआउटपुट:
2 (दो युद्धपोत)।
एक-पास स्कैन (O(1) स्पेस)
केवल युद्धपोत के "हेड" (सबसे ऊपर-बायाँ सेल) गिनें। एक सेल हेड है यदि:
- वह 'X' है।
- उसके ऊपर कोई 'X' नहीं है (या वह पहली पंक्ति है)।
- उसके बाएँ कोई 'X' नहीं है (या वह पहला कॉलम है)।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int ans = 0;
int n = board.size();
int 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;
}
};
int main() {
vector<vector<char>> v = {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
Solution ob;
cout << ob.countBattleships(v); // 2
return 0;
}
इनपुट
[["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
आउटपुट
2
