ধরুন আমাদের একটি 2D বোর্ড আছে, আমাদের গুনতে হবে এতে কতটি যুদ্ধজাহাজ আছে। যুদ্ধজাহাজগুলিকে 'X' চিহ্ন দিয়ে উপস্থাপন করা হয়, খালি স্লটগুলিকে '.' দিয়ে উপস্থাপন করা হয়। আমরা এই নিয়মগুলি অনুমান করতে পারি -
-
আপনি একটি বৈধ বোর্ড পাবেন, শুধুমাত্র যুদ্ধজাহাজ বা খালি স্লট দিয়ে তৈরি।
-
যুদ্ধজাহাজ শুধুমাত্র অনুভূমিকভাবে বা উল্লম্বভাবে স্থাপন করা যেতে পারে। অন্য কথায়, এগুলি শুধুমাত্র 1xN (1 সারি, N কলাম) বা Nx1 (N সারি, 1 কলাম) আকারে তৈরি করা যেতে পারে, যেখানে N যে কোনও আকারের হতে পারে৷
-
দুটি যুদ্ধজাহাজের মধ্যে অন্তত একটি অনুভূমিক বা উল্লম্ব কোষ পৃথক করে - কোন সংলগ্ন যুদ্ধজাহাজ নেই।
তাই যদি বোর্ডটি এরকম হয়:
| X | । | । | X |
| । | । | । | X |
| । | । | । | X |
তাহলে আউটপুট হবে 2, যেহেতু দুটি যুদ্ধজাহাজ আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=0, n :=সারি গণনা এবং m :=কলাম গণনা
-
ith সারির জন্য
-
jth কলামের জন্য
-
যদি বোর্ড[i, j] ডট হয়, তাহলে পরবর্তী পুনরাবৃত্তির জন্য যান
-
যদি i> 0 এবং board[i – 1, j] ='X' হয়, তাহলে পরবর্তী পুনরাবৃত্তির জন্য যান
-
যদি j> 0 এবং বোর্ড[i, j - 1] ='X' হয়, তাহলে পরবর্তী পুনরাবৃত্তির জন্য যান
-
উত্তর 1 দ্বারা বাড়ান
-
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
};
main(){
vector<vector<char>> v = {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
Solution ob;
cout << (ob.countBattleships(v));
} ইনপুট
[["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
আউটপুট
2
