Các trận chiến trong một bảng trong C ++

Giả sử chúng ta có một bảng 2D, chúng ta phải đếm xem có bao nhiêu chiến hạm trong đó. Các thiết giáp hạm được biểu thị bằng ký hiệu 'X', các vị trí trống được biểu thị bằng '.'s. Chúng tôi có thể chấp nhận các quy tắc này -

• Bạn nhận được một bảng hợp lệ, chỉ làm từ các thiết giáp hạm hoặc các khe trống.

• Chỉ có thể đặt tàu chiến theo chiều ngang hoặc chiều dọc. Nói cách khác, chúng chỉ có thể được tạo theo hình dạng 1xN (1 hàng, N cột) hoặc Nx1 (N hàng, 1 cột), trong đó N có thể có kích thước bất kỳ.

• Ít nhất một ô ngang hoặc ô dọc ngăn cách giữa hai thiết giáp hạm - không có thiết giáp hạm nào liền kề.

Vì vậy, nếu bảng giống như:

Sau đó, đầu ra sẽ là 2, vì có hai thiết giáp hạm.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0, n:=số hàng và m:=số cột

• cho hàng thứ i

  • cho cột thứ j

    • nếu bảng [i, j] là dấu chấm, thì hãy chuyển sang lần lặp tiếp theo

    • nếu i> 0 và lên bảng [i - 1, j] =‘X’, thì hãy thực hiện lần lặp tiếp theo

    • nếu j> 0 và board [i, j - 1] =‘X’, thì hãy thực hiện lần lặp tiếp theo

    • tăng ans lên 1

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]

Đầu ra

2