วางระเบิดศัตรูใน C++

สมมติว่าเรามีตาราง 2 มิติ ที่นี่แต่ละช่องเป็นกำแพง 'W' ศัตรู 'E' หรือ '0' ว่างเปล่า เราต้องหาศัตรูสูงสุดที่เราสามารถฆ่าได้โดยใช้ระเบิดลูกเดียว ระเบิดฆ่าศัตรูทั้งหมดในแถวและคอลัมน์เดียวกันจากจุดที่ปลูกจนกระทบผนัง และเราสามารถวางระเบิดได้เฉพาะในช่องว่างเท่านั้น

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 3 เมื่อวางระเบิดที่กรีน มันจะฆ่าศัตรูสามคน

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

• ยกเลิก :=0

• n :=จำนวนแถวของตาราง m :=จำนวนคอลัมน์ของกริด

• กำหนดอาร์เรย์ colCnt ขนาด m

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า j เป็นศูนย์หรือ grid[i, j] เหมือนกับ 'W' ดังนั้น −

      • rowCnt :=0

      • ถ้า grid[i, j] เหมือนกับ 'W' แล้ว −

        • k :=j + 1

      • มิฉะนั้น

        • k :=เจ

      • สำหรับ k

        • rowCnt :=rowCnt + 1 เมื่อ (grid[i, k] คือ 'E') มิฉะนั้น 0

    • ถ้า i เป็นศูนย์ หรือ grid[i, j] เหมือนกับ 'W' ดังนั้น −

      • colCnt[j] :=0

      • ถ้า grid[i, j] เหมือนกับ 'W' แล้ว −

        • k :=ผม + 1

      • มิฉะนั้น

        • k :=ผม

      • สำหรับ k

        • colCnt[j] :=colCnt[j] + 1 เมื่อ (grid[k, j] คือ 'E') มิฉะนั้น 0

    • ถ้า grid[i, j] เหมือนกับ '0' แล้ว −

      • ret :=สูงสุดของ ret และ rowCnt + colCnt[j]

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

3