C++의 폭탄 적

2D 그리드가 있다고 가정하고 여기에서 각 셀은 벽 'W', 적 'E' 또는 비어 있는 '0'입니다. 우리는 하나의 폭탄을 사용하여 죽일 수 있는 최대 적을 찾아야 합니다. 폭탄은 벽에 부딪힐 때까지 심은 지점에서 같은 행과 열에 있는 모든 적을 죽입니다. 그리고 우리는 공백에만 폭탄을 놓을 수 있습니다.

따라서 입력이 다음과 같으면

그러면 출력은 3이 되며 녹색 위치에 폭탄을 배치하면 3명의 적을 죽입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 렛 :=0

• n :=그리드의 행 개수, m :=그리드의 열 개수

• m

  크기의 배열 colCnt 정의

• initialize i :=0의 경우, i

  • j 초기화의 경우:=0, j

    • j가 0이거나 grid[i, j]가 'W'와 같으면 -

      • rowCnt :=0

      • grid[i, j]가 'W'와 같으면 -

        • k :=j + 1

      • 그렇지 않으면

        • k :=j

      • k

        • rowCnt :=rowCnt + 1일 때 (grid[i, k]가 'E'일 때), 그렇지 않으면 0

    • i가 0이거나 grid[i, j]가 'W'와 같으면 -

      • colCnt[j] :=0

      • grid[i, j]가 'W'와 같으면 -

        • k :=나는 + 1

      • 그렇지 않으면

        • k :=나는

      • k

        • colCnt[j] :=colCnt[j] + 1 일 때 (그리드[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