조명될 수 있는 최대 셀 수를 찾는 C++ 프로그램

h * w 차원의 그리드가 주어졌다고 가정합니다. 그리드의 셀에는 전구 또는 장애물이 포함될 수 있습니다. 전구 셀은 오른쪽, 왼쪽, 위, 아래에 있는 셀을 조명하고 장애물 셀이 빛을 차단하지 않는 한 빛이 셀을 통해 비출 수 있습니다. 장애물 셀은 조명을 받을 수 없으며 전구 셀에서 다른 셀에 도달하는 빛을 차단합니다. '#'은 장애물을 나타내고 '.'는 문자열 배열의 그리드가 제공됩니다. 빈 셀을 나타냅니다. 전구가 하나뿐이므로 그리드에 전구를 최적으로 배치하여 밝힐 수 있는 최대 셀 수를 찾아야 합니다.

따라서 입력이 h =4, w =4, grid ={"#...", "....", "...#", "...."}인 경우 출력은 7이 됩니다.

이미지에서 격자에서 조명된 셀을 볼 수 있습니다.

단계

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

Define one 2D array first
for initialize i := 0, when i < h, update (increase i by 1), do:
   count := 0
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if grid[i, j] is same as '#', then:
         count := 0
         Ignore following part, skip to the next iteration
      else:
         first[i, j] := count
         (increase count by 1)
   k := 0
   for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
      if grid[i, j] is same as '#', then:
         k := 0
        Ignore following part, skip to the next iteration
     else:
        k := maximum of k and first[i, j]
        first[i, j] := k
Define one 2D array second
for initialize j := 0, when j < w, update (increase j by 1), do:
   count := 0
   for initialize i := 0, when i < h, update (increase i by 1), do:
      if grid[i, j] is same as '#', then:
         count := 0
         Ignore following part, skip to the next iteration
      else:
         second[i, j] := count
         (increase count by 1)
k := 0
for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
   if grid[i, j] is same as '#', then:
      k := 0
      Ignore following part, skip to the next iteration
   else:
      k := maximum of k and second[i, j]
      second[i, j] := k
result := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      result := maximum of result and first[i, j] + second[i, j]
return result + 1

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

int solve(int h, int w, vector<string> grid){
   vector<vector<int>> first(h, vector<int> (w));
   for(int i = 0; i < h; i++) {
      int count = 0;
      for(int j = 0; j < w; j++) {
         if(grid[i][j] == '#') {
            count = 0;
            continue;
         } else {
            first[i][j] = count;
            count++;
         }
      }
      int k = 0;
      for(int j = w-1; j >= 0; j--) {
         if(grid[i][j] == '#') {
            k = 0;
            continue;
         } else {
            k = max(k, first[i][j]);
            first[i][j] = k;
         }
      }
   }
   vector<vector<int>> second(h, vector<int> (w));
   for(int j = 0; j < w; j++) {
      int count = 0;
      for(int i = 0; i < h; i++) {
         if(grid[i][j] == '#') {
            count = 0;
            continue;
         } else {
            second[i][j] = count;
            count++;
         }
      }
      int k = 0;
      for(int i = h-1; i >= 0; i--) {
         if(grid[i][j] == '#') {
            k = 0;
            continue;
         } else {
            k = max(k, second[i][j]);
            second[i][j] = k;
         }
       }
    }
    int result = 0;
    for(int i = 0; i < h; i++) {
       for(int j = 0; j < w; j++) {
          result = max(result, first[i][j] + second[i][j]);
       }
    }
    return result + 1;
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"#...", "....", "...#", "...."};
   cout<< solve(h, w, grid);
   return 0;
}

입력

4, 4, {"#...", "....", "...#", "...."}

출력

7