Bomb Enemy trong C ++

Giả sử chúng ta có một lưới 2D, ở đây mỗi ô là một bức tường "W", một kẻ thù "E" hoặc trống "0", Chúng ta phải tìm ra kẻ thù tối đa mà chúng ta có thể tiêu diệt bằng một quả bom. Bom tiêu diệt tất cả kẻ thù trong cùng một hàng và cột từ điểm đã trồng cho đến khi nó chạm vào tường. Và chúng ta chỉ có thể đặt bom vào những chỗ trống.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 3, vì đặt bom ở vị trí màu xanh lá cây, nó sẽ giết ba kẻ thù.

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

• ret:=0

• n:=số hàng của lưới, m:=số cột của lưới

• Xác định colCnt mảng có kích thước m

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • nếu j bằng 0 hoặc lưới [i, j] giống với 'W', thì -

      • rowCnt:=0

      • nếu lưới [i, j] giống với 'W', thì -

        • k:=j + 1

      • Nếu không

        • k:=j

      • cho k

        • rowCnt:=rowCnt + 1 khi (lưới [i, k] là 'E'), nếu không thì 0

    • nếu tôi bằng 0 hoặc lưới [i, j] giống với 'W', thì -

      • colCnt [j]:=0

      • nếu lưới [i, j] giống với 'W', thì -

        • k:=i + 1

      • Nếu không

        • k:=i

      • cho k

        • colCnt [j]:=colCnt [j] + 1 khi (lưới [k, j] là 'E') nếu không thì 0

    • nếu lưới [i, j] giống với '0', thì -

      • ret:=tối đa ret và rowCnt + colCnt [j]

• trả lại ret

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxKilledEnemies(vector<vector<char>>& grid) {
      int ret = 0;
      int n = grid.size();
      int m = n ? grid[0].size() : 0;
      int rowCnt = 0;
      vector<int< colCnt(m);
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (!j || grid[i][j] == 'W') {
               rowCnt = 0;
               int k;
               if (grid[i][j] == 'W')
                  k = j + 1;
               else
                  k = j;
               for (; k < m && grid[i][k] != 'W'; k++) {
                  rowCnt += (grid[i][k] == 'E');
               }
            }
            if (!i || grid[i][j] == 'W') {
               colCnt[j] = 0;
               int k;
               if (grid[i][j] == 'W')
                  k = i + 1;
               else
                  k = i;
               for (; k < n && grid[k][j] != 'W'; k++) {
                  colCnt[j] += (grid[k][j] == 'E');
               }
            }
            if (grid[i][j] == '0') {
               ret = max(ret, rowCnt + colCnt[j]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<char>> v = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}};
   cout << (ob.maxKilledEnemies(v));
}

Đầu vào

{{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}

Đầu ra

3