เรือประจัญบานในกระดานใน C++

สมมติว่าเรามีกระดาน 2D เราต้องนับว่ามีเรือประจัญบานอยู่ในนั้นกี่ลำ เรือประจัญบานจะแสดงด้วยสัญลักษณ์ 'X' ช่องว่างจะแสดงด้วย '.' เราสามารถสมมติกฎเหล่านี้ได้ -

• คุณได้รับกระดานที่ถูกต้อง ซึ่งสร้างจากเรือประจัญบานหรือช่องว่าง

• เรือประจัญบานสามารถวางในแนวนอนหรือแนวตั้งเท่านั้น กล่าวคือ สามารถสร้างรูปร่างได้เพียง 1xN (1 แถว, N คอลัมน์) หรือ Nx1 (แถว N, 1 คอลัมน์) โดยที่ N สามารถมีขนาดใดก็ได้

• อย่างน้อยหนึ่งช่องแนวนอนหรือแนวตั้งแยกระหว่างสองเรือประจัญบาน - ไม่มีเรือประจัญบานอยู่ติดกัน

ดังนั้นหากกระดานมีลักษณะดังนี้:

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากมีเรือประจัญบานสองลำ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ans :=0, n :=จำนวนแถวและ m :=จำนวนคอลัมน์

• สำหรับแถวนั้น

  • สำหรับคอลัมน์ที่ j

    • ถ้า board[i, j] เป็นจุด ให้ทำซ้ำต่อไป

    • ถ้า i> 0 และบอร์ด[i – 1, j] ='X' ให้ทำซ้ำต่อไป

    • ถ้า j> 0 และ board[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