Chương trình tìm số lượng tối đa kẻ thù sẽ bị giết để đặt bom trong C ++?

Giả sử chúng ta có một ma trận 2D gồm ba giá trị khác nhau, 2s, 1s và 0s, trong đó giá trị 2 đại diện cho kẻ thù, 1 đại diện cho bức tường và 0 đại diện cho một ô trống. 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ì chúng ta có thể đặt bom vào ô màu xanh lục để tiêu diệt tối đa 3 kẻ thù.

• 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 1 thì:

      • rowCnt:=0

      • nếu lưới [i, j] giống 1, thì:

        • k:=j + 1

      • Nếu không

        • k:=j

      • cho k

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

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

      • colCnt [j]:=0

      • nếu lưới [i, j] giống 1, thì:

        • k:=i + 1

      • Nếu không

        • k:=i

      • cho k

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

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

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

• trả lại ret

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 solve(vector<vector<int>>& 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] == 1) {
               rowCnt = 0;
               int k;
               if (grid[i][j] == 1)
                  k = j + 1;
               else
                  k = j;
               for (; k < m && grid[i][k] != 1; k++) {
                  rowCnt += (grid[i][k] == 2);
               }
            }
            if (!i || grid[i][j] == 1) {
               colCnt[j] = 0;
               int k;
               if (grid[i][j] == 1)
                  k = i + 1;
               else
                  k = i;
               for (; k < n && grid[k][j] != 1; k++) {
                  colCnt[j] += (grid[k][j] == 2);
               }
            }
            if (grid[i][j] == 0) {
               ret = max(ret, rowCnt + colCnt[j]);
            }
         }
      }
      return ret;
   }
};

main(){
   Solution ob;
   vector<vector<int>> v = {
      {0,2,0,0},
      {2,0,1,2},
      {0,2,0,0}};
   cout << (ob.solve(v));
}

Đầu vào

{{0,2,0,0},
{2,0,1,2},
{0,2,0,0}}

Đầu ra

3